# QuickSort.s

	.data		# Data declaration section
array:  .asciiz  "qwertyuiopasdfghjklzxcvbnm"
title:  .asciiz  "Demonstration of QuickSort"
before: .asciiz  "\nString before: "
after:  .asciiz  "\nString  after: "
  
	.text

main:			# Start of code section
        li      $v0, 4
        la      $a0, title
        syscall
        la      $a0, before
        syscall
        la      $a0, array
        syscall
# Call on QuickSort
        la      $a0, array       # Constant pointer to string
        add     $a1, $a0, 0      # Pointer to left end
        add     $a2, $a0, 25     # Pointer to right end
        jal     QS               # The one call from main
# Print out results
        la      $a0, after
        li      $v0, 4
        syscall
        la      $a0, array
        syscall
# End main
        li      $v0, 10
        syscall
##
# Recursive QuickSort
# $a0 -> array (constant) - Global
# $a1 -> left end, $a2 -> right end
##
QS:     sub     $sp, $sp, 16     # \
        sw      $a1, 0($sp)      #  \
        sw      $a2, 4($sp)      #   > Save registers
        sw      $t2, 8($sp)      #  /  
        sw      $ra, 12($sp)     # / and return address
# Basecase
        bge     $a1, $a2, QSret  # Nothing to sort   
# Partition using middle element as pivot
# A[a1..a2] -> A[a1..j-1] | A[j] | A[j+1..a2]
        sub     $t3, $a1, $a0     # index i
        sub     $t4, $a2, $a0     # index j
        add     $t0, $t3, $t4     # t0 = i+j choose middle
        sra     $t0, $t0, 1       # t0 = (i+j) div 2
        add     $t0, $t0, $a0     # t0 -> A[(i+j) div 2]
        lb      $t5, 0($t0)       # t5 = pivot value 
        lb      $t6, 0($a1)       # t6 = A[i] = left element
        sb      $t5, 0($a1)       # Swap them so pivot
        sb      $t6, 0($t0)       # is first element
# 
        move    $t1, $a1         # Initially i -> first (pivot) item a1
        add     $t2, $a2, 1      # Initially j -> just past last item a2
        lb      $t0, 0($a1)      # Pivot value in t0 (in $t5)
# 
loop:
# 
i_loop: add     $t1, $t1, 1      # i=i+1;
        lb      $t5, 0($t1)      # t5 = A[i]
        bgt     $t0, $t5, i_loop # until pivot <= A[i]
j_loop: sub     $t2, $t2, 1      # j=j-1; 
        lb      $t6, 0($t2)      # t6 = A[j]
        blt     $t0, $t6, j_loop # until pivot >= A[j]
# 
        bge     $t1, $t2, test   # if i<j swap
# 
        sb      $t6, 0($t1)      # A[i] and
        sb      $t5, 0($t2)      # A[j]
# 
test:   blt     $t1, $t2, loop   # until i >= j
# 
        lb      $t5, 0($a1)      # swap a[a1] = pivot
        lb      $t6, 0($t2)      # and a[j]
        sb      $t5, 0($t2)      # now a[j] is
        sb      $t6, 0($a1)      # in its final position
# Done with partition
        lw      $a1, 0($sp)
        sub     $a2, $t2, 1
        jal     QS               # Recursive call on left
        add     $a1, $t2, 1
        lw      $a2, 4($sp)
        jal     QS               # Recursive call on right
# 
QSret:  lw      $ra, 12($sp)     # \Replace return address
        lw      $t2, 8($sp)      #  \
        lw      $a2, 4($sp)      #   > and registers
        lw      $a1, 0($sp)      #  /
        add     $sp, $sp, 16     # /
        jr      $ra
## END OF QuickSort.s
############################################################
# This is the classic Quicksort invented by Hoare in 1962.
# It is the standard example of the "divide-and-conquer" 
# technique using recursion. It is the fastest (on average)
# sorting method O(n log n) although its worst case is O(n^2).
# Choosing one element as "pivot" (we have picked the middle
# element of the array to avoid a problem with already sorted
# files), we partition the array A[m..n] at index p so that
# all elements to the left of A[p] are no larger and all 
# elements to its right are no smaller:
#         A[m..n] -> A[m..p-1] | A[p] | A[p+1..n]
# and then recursively sort the two subarrays. It is also
# a particularly good method since it sorts the array in 
# place, needing no significant extra space.
############################################################
# This version could be extended to handle data from a file
# (see Chapter Six). In order to modify it to work with
# numerical data, it would be necessary to carefully change
# the index manipulations to handle 4 byte data. In particular,
# alignment problems must be addressed (see the code to find
# the middle element, for example). 
############################################################
############################################################