# implement quicksort in MIPS, Lin Jensen, April 2010
#  updated: March 2014, with rand() -random number
#		Using .macro to shorten code - push and pop

	.include	"stackmacros"
.text
.globl __start
__start:		# testing main program
la	$a0,first
la	$a1,last
jal 	quicksort

la	$t0,first
la	$t1,last

printloop:
	lw $a0,($t0)
	li $v0, 1
	syscall		# print each number
	la $a0,comma	# and ", "
	li $v0,4
	syscall
	add	$t0, $t0, 4	#next number
	ble	$t0, $t1,printloop

	la	$a0,endl
	syscall
	li $v0,10
	syscall
#---------------------------------------------------

quicksort:	# an array, args point to first and last elements
		#
		# note: partition returns:
		#	v0 - head of second sublist (i)
		#	v1 - tail of first  sublist (j)
		
	blt	$a0,$a1,doq
	jr $ra			# else nothing to do
doq:
	sub	$sp,$sp, 16		# 4 words "stack frame"
	sw	$a0,($sp)
	sw	$a1,4($sp)
	sw	$ra,8($sp)
	#	   12($sp)  - space to save v0 for second call

jal partition
move $a1, $v1	#sort first half
		# must save our $v0! 
	sw	$v0, 12($sp)
jal quicksort
	lw	$a0,12($sp)		#sort 2nd half
	lw	$a1,4($sp)
jal quicksort

	lw	$a0,($sp)
	lw	$a1,4($sp)
	lw	$ra,8($sp)
	add	$sp, $sp, 16
	jr $ra
#---------------------------------------------------
# arrange array into 2 parts, bup to a randomly chosen value, 
#  and beyond it, with the chosen element between.
#  This guarantees that the longest list is at least 1 shorter
partition:
	# an array, args point to first and last elements
	#
	# Returns:
	#	v0 - head of second sublist (i) "up pointer"
	#	v1 - tail of first  sublist (j) "down pointer"

# pick an array element at random.

	push	$ra
	jal rand	#v0 is a random (positive) number
	pop	$ra

	sub $t0,$a1,$a0		# offset of tail element
	add $t0,$t0,4		#length of array in bytes	
	sra $t0,$t0,2		# ... in words n
	rem $t0, $v0, $t0	#  0<= t0 < n
	sll $t0,$t0,2		#  an offset in bytes
	add $t0,$a0,$t0	# t0 is pivot location (may neet to move at end)
	lw  $t1,($t0)	#$t1 is pivot value

#we will need to do some swaps, based upon pointers
	.macro	swap	%x  %y
	lw	$t8, (%x)
	lw	$t9, (%y)
	sw	$t9, (%x)
	sw	$t8, (%y)
	.end_macro

# Scan from both ends of array, when pairs out of order, swap them
# Until the pointers cross.

	move $v1,$a1	#down pointer	(j)	to be returned
	move $v0,$a0	#up pointer	(i)	as sublist limits
pwhile:
down:			#find next out of order item on high side
	lw $t2,($v1)
	blt $t2,$t1, up	# out of order, too small
	sub	$v1, $v1, 4	# scan down
	bge     $v1, $a0, down    #could finally end up < a0

up:	
	lw $t2,($v0)
	bgt $t2,$t1, change	# out of order, too large
	add	$v0, $v0, 4	# scan up
	ble     $v0,$a1, up	# guard against out of range compare.
change:
	blt	$v1,$v0,pdone	# pointers have crossed, we are done
	#v0==v1 not possible, since elem there cant be bigger and smaller!
#	swap the two out of order-s
	swap	$v0  $v1

	j	pwhile
pdone:	
# now move pivot to end of the range it may be in
	bgt	$t0,$v1, other	# if pivot within left list
				# swap it to the end
	 swap	$t0, $v1
	  sub	$v1, $v1, 4	#  and remove pivot from further sorting
other:
	blt	$t0, $v0, pret	# if pivot within right list, same thing
	 swap	$t0, $v0
	  add	$v0, ,$v0, 4		# and removed from further sorting
		 
# Note: it may well be unnecessary to move the pivot value.
pret:
	jr	$ra
#--------------------------------
#  A Random number generator
#  Linear congruential
# starts with a "seed" > 0
#
# new = (a*old + c) mod m
#
# a and c should be relatively prime, m can be a power of 2
#
#  Lin Jensen
       	
rand:
       	lw $v0, seed
       	mul $v0,$v0,11		# 11 * seed
       	add $v0,$v0,47		# (11*seed + 47)
       	and $v0,$v0,0x3fff	#mod 1K or 2^14
       	sw  $v0, seed		# new seed
       	sra $v0, $v0,3		# low order bits are less random
       	jr  $ra

.data
first: .word 23,15,6,-8,9,8,1,2,96
last:  .word 30
seed:	.word 421   #used by rand     
comma: .asciiz ", "
endl:  .asciiz "\n"

#2, 1, -8, 9, 6, 15, 8, 23, 30, 96,