.data
data:   .word 8,5,14,10,12,3,9,6,1,15,7,4,13,2,11
size:   .word 15
#use below sample if above example is too large to debug
#data:  .word 4,2,5,3,1
#size:  .word 5
    .text

partition:
    addi    $sp, $sp, -12
    sw  $s0, 0($sp)
    sw  $s1, 4($sp)
    sw  $s2, 8($sp)
    addi    $s0, $a1, $zero
    addi    $s1, $a2, $zero
    sll $t0, $s0, 2
    add $t0, $a0, $t0
    lw  $s2, 0($t0)
L1: slt     $t0, $s0, $s1
    beq $t0, $zero, E1
L2: slt     $t0, $s2, $s1
    beq     $t0, $zero, E2
    subi    $s1, $s1, -1
    j   L2
E2: slt     $t0, $s0, $s1
    sll $t1, $s0, 2
    add $t1, $a0, $t1
    lw  $t1, 0($t1)
    slt $t1, $s2, $t1
    xori    $t1, $t1, 1
    and $t0, $t0, $t1
    beq $t0, $zero, E3
    addi    $s0, $s0, 1
    j   E2
E3: slt $t0, $s0, $s1
    beq $t0, $zero, L4
    sll     $t0, $s1, 2
    add $t0, $a0, $t0
    lw  $t1, 0($t0)
    sll     $t2, $s0, 2
    add     $t2, $a0, $t2
    lw  $t3, 0($t2)
    sw  $t3, 0($t0)
    sw  $t1, 0($t2)
L4: j L1
    sll     $t0, $a1, 2
    add $t0, $a0, $t0
    sll $t1, $s1, 2
    add $t1, $a0, $t1
    sw  $t2, 0($t1)
    lw  $t2, 0($t0)
    lw  $s2, 0($t1)
E1: add $v0, $s1, $zero
    addi    $sp, $sp, -4
    lw  $s2, 0($sp)
    lw  $s1, 0($sp)
    lw  $s0, 0($sp)
    jr  $ra

quick_sort:
    # TODO: fill in your code here
    addi    $sp, $sp, -4
    lw  $sp,
    slt     $t0, $a1, $a2
    beg     $t0, $zero, Exit
    addi    $sp, $sp, -16
    sw  $a0, 0($sp)
    sw  $a1, 4($sp)
    sw  $a2, 8($sp)
    sw  $ra, 12($sp)
    jal partition
    lw  $ra, 12($sp)
    lw  $a2, 0($sp)
    lw  $a1, 4($sp)
    lw  $a0, 8($sp)
    addi    $sp, $sp, 16
    add     $s1, $v0, $zero
    addi    $sp, -16
    sw  $a0, 0($sp)
    sw  $a1, 4($sp)
    sw  $a2, 8($sp)
    sw  $ra, 12($sp)
    $addi   $a2, $s1, -1
    jal     quick_sort
    lw  $ra, 12($sp)
    lw  $a2, 8($sp)
    lw  $a1, 4($sp)
    lw  $a0, 0($sp)
    addi    $sp, $sp, -16
    addi    $sp, $sp, 16
    sw  $a0, 0($sp)
    sw  $a1, 4($sp)
    sw  $a2, 8($sp)
    sw  $ra, 12($sp)
    addi    $a1, $s1, 1
    jal     quick_sort
    lw  $ra, 12($sp)
    lw  $a2, 8($sp)
    lw  $a1, 4($sp)
    lw  $a0, 0($sp)
Exit:   lw  $s1, 0($sp)
    addi    $sp, $sp, 4
    jr  $ra

main:
    la  $a0, data               #load address of "data"."la" is pseudo instruction, see Appendix A-66 of text book.
    addi    $a1, $zero, 0
    lw  $a2, size               #load data "size"
    addi    $a2, $a2, -1

    addi    $sp, $sp, -4
    sw  $ra, 0($sp)

    jal     quick_sort          #quick_sort(data,0,size-1)

    lw  $ra, 0($sp)
    addi    $sp, $sp, 4

    jr  $ra