# Quick Sort - MIPS
# By: Odis

.data

numbers: .word 8,2,7,1,5,6,3,4,9,0
length:  .word 10
str:	   .asciiz " "
str1:    .asciiz "8 2 7 1 5 6 3 4 9 0\n"
str2:	   .asciiz "\n"

.text
.globl main

main:
    la $a0, numbers     # $a0 = array
    move $a1, $zero     # $a1 = 0

    lw $a2, length		# $a2 = length
    sub $a2,$a2,1       # length-1

    jal qsort           # qsort( array, 0, n-1 )
	
	 #print the array
    la $a0,str1         # Print of str1, starting array, for comparison
    li $v0,4                 
    syscall                  

	 # print new sorted array
    la $t2,numbers
    lw $t4,length
    li $t3,0

for_print:

    bge  $t3, $t4, exit_print  # if test >= length go to exit_print

    sll $t1, $t3, 2            # $t1 = test*4
    add $t1, $t1, $t2          # $t2 = numbers + test*4

    lw   $a0,0($t1)
    li   $v0,1                 # print of the element numbers[test]
    syscall                  

    la   $a0,str               # print newline
    li   $v0,4
    syscall

    addi $t3,$t3,1             # test = test + 1
    j    for_print

exit_print:

   li $v0,10                   # syscall to exit
   syscall

#qsort function
#a0 = array, a1 = low, a2 = high
qsort:
   # create stack frame and save vals
   addi $sp, $sp, -16

   sw   $ra, 0($sp)
   sw   $s0, 12($sp)
   sw   $s1, 8($sp)
   sw   $s2, 4($sp)

   ###

	bge $a1,$a2,end_qsort_if	# if low >= high, endif
    
	#save contents in s registers
	#s0 = array, s1 = low, s2 = high
	move $s0,$a0
	move $s1,$a1
	move $s2,$a2

	jal partition

	move $s3,$v0			# store pivotPosition in $s3
	sub  $t0,$s3,1			# pivotPosition-1 = $t0
	
	move $a0,$s0
	move $a1,$s1
	move $a2,$t0

	jal qsort

	move $a0,$s0
	addi $a1,$s3,1
	move $a2,$s2

	jal qsort

end_qsort_if:

   # restore values
	lw   $ra, 0($sp)
	lw   $s0, 12($sp)
	lw   $s1, 8($sp)
	lw   $s2, 4($sp)

	addi $sp, $sp, 16

   ###

	jr $ra            #return


# do some swapping, return "right" in $v0
# a0 = array, a1 = low, a2 = high
partition:
   # create stack frame and save vals
	addi $sp, $sp, -24

	sw   $ra, 4($sp)
	sw   $s0, 8($sp)
	sw   $s1, 12($sp)
	sw   $s2, 16($sp)
	sw   $s3, 20($sp)
	sw   $s4, 0($sp)

   ###

	move $s0, $a0	#s0 = array
	move $s1, $a1	#s1 = low
	move $s4, $s1	#s4 = left
	move $s2, $a2  #s2 = right

	move $s3,$s1   #s3 = pivot = array[low]
	sll  $s3,$s1,2
	add  $s3,$s0,$s3
	lw   $s3, 0($s3)

master_while:

	bge  $s4,$s2,end_master_while		# if left >= right, end while

 right_while:
	move $t6,$s2      #t6 = array[right] address
	sll  $t6,$t6,2
	add  $t6,$s0,$t6
	lw   $t7,0($t6)   #t7 = array[right]

	ble  $t7,$s3,end_right_while	   # if array[right] <= pivot, break
	sub  $s2,$s2,1                   # right--
	j	right_while
 end_right_while:

 left_while:
	move $t4,$s4                     #t4 = array[left] address
	sll  $t4,$t4,2
	add  $t4,$s0,$t4
	lw   $t5,0($t4)                  #t5 = array[left]

	bge  $s4,$s2,end_left_while		# if left >= right
	bgt  $t5,$s3,end_left_while		# or array[left] <= pivot, break

   add  $s4,$s4,1                   # left++
	j    left_while

 end_left_while:            

	bge  $s4,$s2,master_while        # if left >= right, loop

	move $a0,$s0                     # a0 = array
	move $a1,$s4                     # a1 = left
	move $a2,$s2                     # a2 = right

	jal  swap

	j    master_while

end_master_while:
	move $t5,$s1      #t5 = array[low]
	sll  $t5,$t5,2
	add  $t5,$s0,$t5

	move $t6,$s2      #t6 = array[right] address
	sll  $t6,$t6,2
	add  $t6,$s0,$t6
	lw   $t7,0($t6)	#t7 = array[right]

	sw   $t7,0($t5)	#array[low] = array[right]
	sw   $s3,0($t6)   #array[high] = pivot

	move $v0,$s2      # return right

   # restore values
	lw   $ra, 4($sp)
	lw   $s0, 8($sp)
	lw   $s1, 12($sp)
	lw   $s2, 16($sp)
	lw   $s3, 20($sp)
	lw   $s4, 0($sp)

	addi $sp, $sp, 24

   ###

	jr   $ra

# swaps the array elements
# parameters are array (v), low index(i), high index(j)
swap:
   sll $t1, $a1, 2      # $t1=i*4
   add $t1, $t1, $a0    # $t1=v+i*4
   lw  $t0, 0($t1)      # $t0=v[i] 

   sll $t2, $a2, 2      # $t2=j*4
   add $t2, $t2, $a0    # $t2=v+j*4
   lw  $t3, 0($t2)      # $t3=v[j]

   sw  $t3, 0($t1)      # v[i]=$t3  
   sw  $t0, 0($t2)      # v[j]=$t0

   jr  $ra