swap:
        lw      $t0, $a0            # load args into t0, t1
        lw      $t1, $a1
        sw      $t0, $a1            # store t0, t1 in a1, a0
        sw      $t1, $a0

comp_largest:
        add     $v0, $zero, $a2     # res=a2
        slt     $t5, $a0, $a1
        beq     $t5, $zero, exit_comp

        sll     $t3, $a0, 2         # t3 = a0*4
        add     $t3, $t3, $a3       # t3 = loc of a0*4 in arr
        lw      $t3, 0($t3)         # t3 = item in arr + a0*4

        sll     $t4, $a2, 2         # t4 = a2*4
        add     $t4, $t4, $a3
        lw      $t4, 0($t4)         # t4 = item in arr + a2*4

        slt     $t5, $t4, $t3
        beq     $t5, $zero, exit_comp
        add     $v0, $zero, $a0     # if t4 < t3, res = a0
exit_comp: j    $ra

heapify:
        addi    $sp, $sp, -16       # room for 4 vars
        sw      $ra, 12($sp)        # store saved vars
        sw      $s2, 8($sp)
        sw      $s1, 4($sp)
        sw      $s0, 0($sp)

        add     $s0, $zero, $a0     # store args in saved vars
        add     $s1, $zero, $a1
        add     $s2, $zero, $a2

        add     $t0, $zero, $s2     # t0 = largest = i

        add     $t1, $zero, $s2
        sll     $t1, $t1, 1
        addi    $t1, $t1, 1         # t1 = i*2 + 1

        add     $t2, $zero, $s2
        sll     $t2, $t2, 1
        addi    $t2, $t2, 2         # t2 = i * 2 + 2

        add     $a0, $zero, $t1     # a0 = t1
        add     $a1, $zero, $s1     # a1 = s1
        add     $a2, $zero, $t0     # a2 = t0 = largest
        add     $a3, $zero, $s0     # a3 = s0 = array

        j comp_largest

        add     $a0, $zero, $t2     # a0 = t2
        add     $a2, $zero, $v0     # a2 = v0 = largest = t0 or t1

        j comp_largest              # largest in $v0

        beq     $s2, $v0, exit      # if largest didn't change, exit

        sll     $a0, $s2, 2         # a0 = s2 * 4
        add     $a0, $a0, $s0       # a0 = location of s2*4 in arr

        sll     $a1, $v0, 2         # a1 = v0 * 4
        add     $a1, $a1, $s0       # a1 = location of v0*4 in arr

        j swap

        add     $a0, $zero, $s0     # set up args for recursive call
        add     $a1, $zero, $s1
        add     $a2, $zero, $v0

        j       heapify

exit:   lw      $s0, 0($sp)         # get variables from stack
        lw      $s1, 4($sp)
        lw      $s2, 8($sp)
        lw      $ra, 12($sp)
        addi    $sp, $sp, 16        # pop 4 items
        j       $ra

heapsort:
        addi    $sp, $sp, -16       # space for 4 items
        sw      $ra, 12($sp)        # store ra, s0, s1, s2
        sw      $s2, 8($sp)
        sw      $s1, 4($sp)
        sw      $s0, 0($sp)

        add     $s0, $zero, $a0
        add     $s1, $zero, $a1

        add     $s2, $zero, $s1     # s2 = n
        srl     $s2, $s2, 1         # s2 = n / 2
        addi    $t0, $t0, -1        # s2 = n / 2 - 1

loop1:  slt     $t1, $zero, $s2     # 0 < s2
        beq     $t1, $zero, exit1   # if s2 < 0 exit
        add     $a0, $zero, $s0     # args for heapify
        add     $a1, $zero, $s1
        add     $a2, $zero, $s2
        j       heapify
        addi    $s2, $s2, -1        # s2 -= 1
        j       loop1

exit1:  add     $s2, $zero, $s1     # s2 = n
        addi    $s2, $s2, -1        # s2 = n - 1

loop2:  slt     $t1, $zero, $s2     # 0 < s2
        beq     $t1, $zero, exit2   # if s2 < 0 exit

        add     $a0, $zero, $s0     # location of first item of arr

        add     $a1, $zero, $s2     # a1 = s2
        sll     $a1, $a1, 2         # a1 = s2 * 4
        add     $a1, $a1, $s0       # location of s2th item of arr

        j       swap

        add     $a0, $zero, $s0     # args for heapify
        add     $a1, $zero, $s2
        add     $a2, $zero, $zero

        j       heapify

        addi    $s2, $s2, -1        # s2 -= 1
        j       loop2

exit2:  lw      $s0, 0($sp)         # get vars from stack
        lw      $s1, 4($sp)
        lw      $s2, 8($sp)
        lw      $ra, 12($sp)
        addi    $sp, $sp, 16        # pop 4 items
        j       $ra