/*
 * C Program sorts the numbers in ascending order using insertion sort (insertion_sort.c)
 */
/*
#include <stdio.h>
#define MAXSIZE 1000

void insertion_sort(int list[], int size) {
    int temp, i, j;
    for (i = 1; i < size; i++) {
        temp = list[i];
        j = i - 1;                         // check left part
        while (temp < list[j] && j >= 0) { // find position for putting temp
            list[j + 1] = list[j];         // shift elements of left part to right
            j = j - 1;                     // the first list[j + 1] is saved in temp
        }
        list[j + 1] = temp;                // insert temp in j + 1
    }
}

int main() {
    int array[MAXSIZE];
    int i, num;

    printf("enter the number of elements n = ");
    scanf("%d", &num);
    printf("enter %d elements one by one\n", num);
    for (i = 0; i < num; i++) {
        scanf("%d", &array[i]);
    }
    printf("\nthe original array is   ");
    for (i = 0; i < num; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    insertion_sort(array, num);

    printf("the  sorted  array is   ");
    for (i = 0; i < num; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}
*/

.text
insertion_sort:
	addiu	$sp,$sp,-24
	sw	$fp,20($sp)
	move	$fp,$sp
	sw	$4,24($fp)
	sw	$5,28($fp)
	li	$2,1
	sw	$2,0($fp)
	j	$L2
	nop
$L6:
	lw	$2,0($fp)
	nop
	sll	$2,$2,2
	lw	$3,24($fp)
	nop
	addu	$2,$3,$2
	lw	$2,0($2)
	nop
	sw	$2,8($fp)
	lw	$2,0($fp)
	nop
	addiu	$2,$2,-1
	sw	$2,4($fp)
	j	$L3
	nop
$L5:
	lw	$2,4($fp)
	nop
	addiu	$2,$2,1
	sll	$2,$2,2
	lw	$3,24($fp)
	nop
	addu	$2,$3,$2
	lw	$3,4($fp)
	nop
	sll	$3,$3,2
	lw	$4,24($fp)
	nop
	addu	$3,$4,$3
	lw	$3,0($3)
	nop
	sw	$3,0($2)
	lw	$2,4($fp)
	nop
	addiu	$2,$2,-1
	sw	$2,4($fp)
$L3:
	lw	$2,4($fp)
	nop
	sll	$2,$2,2
	lw	$3,24($fp)
	nop
	addu	$2,$3,$2
	lw	$3,0($2)
	lw	$2,8($fp)
	nop
	slt	$2,$2,$3
	beq	$2,$0,$L4
	nop
	lw	$2,4($fp)
	nop
	bgez	$2,$L5
	nop
$L4:
	lw	$2,4($fp)
	nop
	addiu	$2,$2,1
	sll	$2,$2,2
	lw	$3,24($fp)
	nop
	addu	$2,$3,$2
	lw	$3,8($fp)
	nop
	sw	$3,0($2)
	lw	$2,0($fp)
	nop
	addiu	$2,$2,1
	sw	$2,0($fp)
$L2:
	lw	$3,0($fp)
	lw	$2,28($fp)
	nop
	slt	$2,$3,$2
	bne	$2,$0,$L6
	nop
	move	$sp,$fp
	lw	$fp,20($sp)
	addiu	$sp,$sp,24
	j	$31
	nop
main:
	addiu	$sp,$sp,-4032
	sw	$31,4028($sp)
	sw	$fp,4024($sp)
	move	$fp,$sp
	lui	$2,%hi($LC0)
	addiu	$4,$2,%lo($LC0)
	jal	printf
	nop
	addiu	$3,$fp,4020
	lui	$2,%hi($LC1)
	addiu	$4,$2,%lo($LC1)
	move	$5,$3
	jal	scanf
	nop
	lw	$3,4020($fp)
	lui	$2,%hi($LC2)
	addiu	$4,$2,%lo($LC2)
	move	$5,$3
	jal	printf
	nop
	sw	$0,16($fp)
	j	$L8
	nop
$L9:
	addiu	$3,$fp,20
	lw	$2,16($fp)
	nop
	sll	$2,$2,2
	addu	$3,$3,$2
	lui	$2,%hi($LC1)
	addiu	$4,$2,%lo($LC1)
	move	$5,$3
	jal	scanf
	nop
	lw	$2,16($fp)
	nop
	addiu	$2,$2,1
	sw	$2,16($fp)
$L8:
	lw	$2,4020($fp)
	lw	$3,16($fp)
	nop
	slt	$2,$3,$2
	bne	$2,$0,$L9
	nop
	lui	$2,%hi($LC3)
	addiu	$4,$2,%lo($LC3)
	jal	printf
	nop
	sw	$0,16($fp)
	j	$L10
	nop
$L11:
	lw	$2,16($fp)
	nop
	sll	$2,$2,2
	addiu	$3,$fp,16
	addu	$2,$3,$2
	lw	$3,4($2)
	lui	$2,%hi($LC4)
	addiu	$4,$2,%lo($LC4)
	move	$5,$3
	jal	printf
	nop
	lw	$2,16($fp)
	nop
	addiu	$2,$2,1
	sw	$2,16($fp)
$L10:
	lw	$2,4020($fp)
	lw	$3,16($fp)
	nop
	slt	$2,$3,$2
	bne	$2,$0,$L11
	nop
	li	$4,10
	jal	putchar
	nop
	lw	$2,4020($fp)
	addiu	$3,$fp,20
	move	$4,$3
	move	$5,$2
	jal	insertion_sort
	nop
	lui	$2,%hi($LC5)
	addiu	$4,$2,%lo($LC5)
	jal	printf
	nop
	sw	$0,16($fp)
	j	$L12
	nop
$L13:
	lw	$2,16($fp)
	nop
	sll	$2,$2,2
	addiu	$3,$fp,16
	addu	$2,$3,$2
	lw	$3,4($2)
	lui	$2,%hi($LC4)
	addiu	$4,$2,%lo($LC4)
	move	$5,$3
	jal	printf
	nop
	lw	$2,16($fp)
	nop
	addiu	$2,$2,1
	sw	$2,16($fp)
$L12:
	lw	$2,4020($fp)
	lw	$3,16($fp)
	nop
	slt	$2,$3,$2
	bne	$2,$0,$L13
	nop
	li	$4,10
	jal	putchar
	nop
	move	$2,$0
	move	$sp,$fp
	lw	$31,4028($sp)
	lw	$fp,4024($sp)
	addiu	$sp,$sp,4032
	j	$31
	nop
.data
$LC0:	.ascii	"enter the number of elements n = \000"
$LC1:	.ascii	"%d\000"
$LC2:	.ascii	"enter %d elements one by one\012\000"
$LC3:	.ascii	"\012the original array is   \000"
$LC4:	.ascii	"%d \000"
$LC5:	.ascii	"the  sorted  array is   \000"
.end