example MIPS assembly: insertion sort

insertion_sort.asm

.data # data section

data: .word 132470, 324545, -4, 73245, 93245, 80324542, 244, 2, 66, 236, 327, -7, 236, 21544
size: .word 14
spacebar: .asciiz " "

.text # text section

.globl main # call main by SPIM

rec_insertion_sort:
# saved return address & frame pointer
addiu $sp, $sp, -4
sw $ra, 0($sp)
addiu $sp, $sp, -4
sw $fp, 0($sp)
addu $fp, $sp, $0

# saved for avoid overwrite
addiu $sp, $sp, -8
sw $s0, 0($sp)  # saved for key
sw $s2, 4($sp)  # saved for x

# init
li $s0, 0 # key
li $s1, 0 # i
li $s2, 0 # x
li $t1, 1 # temp = 1

# load argument
lw $a0, 8($fp)

sltu $t2, $t1, $a0 # maxIndex > 1
beq $t2, $0, first_return

# change to new argument
addiu $s4, $a0, -1 # maxIndex - 1
addiu $sp, $sp, -4
sw $s4, 0($sp)

jal rec_insertion_sort
# back
addiu $sp, $sp, 4
# get return value to `x`
addu $s2, $v0, $0
# load data from memory
la	$t0, data
sll $t3, $s2, 2 # x * 4
# change data to data[x]
addu $t1, $t0, $t3
# load data[x] to key
lw $s0, 0($t1)
addiu $s1, $s2, -1 # i = x - 1

# add condition of while loop
while:
# set value of i
sll $t3, $s1, 2 # i * 4
# change data to data[i]
addu $t1, $t0, $t3
# first condition
slt $t2, $s1, $0  # i < 0
bne $t2, $0, end_while
# second condition
lw $t5, 0($t1) # t5 is data[i]
slt $t3, $s0, $t5 # key < data[i]
beq $t3, $0, end_while

# in while loop
sw $t5 4($t1)      # data[i+1] = data[i]
addiu $s1, $s1, -1 # i--

j while
end_while:

sw $s0, 4($t1)    # data[i+1] = key
addiu $v0, $s2, 1 # return x + 1
j end

first_return:
addu $v0, $0, $a0 # return maxIndex
end:
# restore back
lw $s0, 0($sp)  # restore for key
addiu $sp, $sp, 4
lw $s2, 0($sp)  # restore for x
addiu $sp, $sp, 4
lw $fp, 0($sp)  # restore for fp
addiu $sp, $sp, 4
lw $ra, 0($sp)  # restore for ra
addiu $sp, $sp, 4
jr $ra

# -------------------------------------------------------------

main:
la	$t0, data
# size of data
lw $t6, size

# add argument
addiu $sp, $sp, -4
sw $t6, 0($sp)

jal rec_insertion_sort
# back
addiu $sp, $sp, 4
# assign $t1 = 0 <- `i`
li $t1, 0

loop:
sltu $t7, $t1, $t6
beq $t7, $0, end_main

# add data into $a0
lw $a0, ($t0)
addiu $t0, $t0, 4

# print integer in a0
li	$v0, 1
syscall
# print spacebar
la	$a0, spacebar
li  $v0, 4
syscall

addiu $t1, $t1, 1 # i++
j loop

end_main:
li $v0 10
syscall