There is a bug in this code, i cant find the bug, please help me find the bug, and tell me how to fix it. This is a code for quick sort algorithm implemented in MIPS. If i run this code, it gives me the output: 1 2 3 4 5 6 7 10 9 8 rather than 1 2 3 4 5 6 7 8 9 10

# This code contains three procedures: qs that performs quicksort, partition that # "partitions" the array based on the pivot (end of the input array) and swap, # which swaps two different locations in memory

# to use the code, we need to initialize an integer array v[n] # then put the base address of that array in $a0, the start index in $a1, and the end index in $a2

.data

smallTable: .word 7,8,1,9,2,6,3,10,4,5 .text

# test quicksort with smallTable la $a0, smallTable li $a1, 0 li $a2, 9 jal partition # terminate li $v0, 10 syscall

#void quicksort (int v[], int start, int end){ # if (start < end){ # int q = partition(v, start, end); # quicksort(v, start, q - 1); # quicksort(v,q + 1,end); # } #} # arguments: $a0 = v[], $a1 = start, $a2 = end # saved variables: $s0 = q, $s1 = v[], $s2 = start, $s3 = end qs: addi $sp,$sp, -20 sw $ra, 16($sp) sw $s3,12($sp) # save $s3 on stack sw $s2, 8($sp) # save $s2 on stack sw $s1, 4($sp) # save $s1s on stack sw $s0, 0($sp) # save $s0 on stack ################################################### # YOUR CODE HERE move $s1, $a0 move $s2, $a1 #start move $s3, $a2 #end slt $t0, $s2, $s3 beq $t0, $zero, done add $a0, $s1, $zero add $a1, $s2, $zero add $a2, $s3, $zero jal partition move $s0, $v0 #pivot lw $s2, 8($sp) move $a1, $s2 addi $a2, $s0, -1 jal qs addi $a1, $s0, 1 lw $s3,12($sp) add $a2, $s3, $zero jal qs ###################################################

done: lw $s0, 0($sp) # restore $s0 from stack lw $s1, 4($sp) # restore $s1 from stack lw $s2, 8($sp) # restore $s2 from stack lw $s3,12($sp) # restore $s3 from stack lw $ra,16($sp) # restore $ra from stack addi $sp,$sp, 20 # restore stack pointer

jr $ra

#int partition (int v[], int start, int end){ # int pivot = v[end]; # int i = start; # for (int j = start; j < end; j++ ){ # if (v[j] <= pivot){ # swap(v,i,j); # i++; # } # } # swap(v, i, end); # return i; #} # arguments: $a0 for v[], $a1 = start, $a2 = end # saved values: $s0 for pivot, $s1 for i, $s2 for j, $s3 for v[], $s4 for start, $s5 for end # return value: $v0 for return i partition: addi $sp,$sp, -28 sw $ra, 24($sp) sw $s5, 20($sp) sw $s4, 16($sp) sw $s3,12($sp) # save $s3 on stack sw $s2, 8($sp) # save $s2 on stack sw $s1, 4($sp) # save $s1 on stack sw $s0, 0($sp) # save $s0 on stack

################################################### # YOUR CODE HERE move $s3, $a0 #v[] move $s4, $a1 #low/start move $s5, $a2 #high/end sll $t0, $s5, 2 add $t0, $s3, $t0 lw $s0, 0($t0) #$ s0 = pivot add $s1, $s4, $zero #i add $s2, $s4, $zero # j forloop: slt $t1, $s2, $s5 # check if j

exit2: addi $s2, $s2, 1 #j++ j forloop exit1: move $a0, $s3 move $a1, $s1 move $a2, $s5 #v0 = i+1 return (i + 1); jal swap add $v0, $zero, $s1 ################################################### lw $s0, 0($sp) # restore $s0 from stack lw $s1, 4($sp) # restore $s1 from stack lw $s2, 8($sp) # restore $s2 from stack lw $s3,12($sp) # restore $s3 from stack lw $s4,16($sp) lw $s5,20($sp) lw $ra,24($sp) # restore $ra from stack addi $sp,$sp, 28 # restore stack pointer

jr $ra # swap procedure: $a0 is address of array, $a1 is k, $a2 is j swap: ################################################### # YOUR CODE HERE sll $t1, $a1, 2 #t1 = 4a add $t1, $a0, $t1 #t1 = arr + 4a lw $t0, 0($t1) #s3 t = array[a]

sll $t2, $a2, 2 #t2 = 4b add $t2, $a0, $t2 #t2 = arr + 4b lw $t3, 0($t2) #s4 = arr[b]

sw $t3, 0($t1) #arr[a] = arr[b] sw $t0, 0($t2) #arr[b] = t

jr $ra #jump back to the caller

###################################################