# CSCI 424, Homework 3
# Adam Carpenter - username acarpent - acarpenter@email.wm.edu
	.text
	.globl	main
main:
	la	$s0, array1 		# create array
	la	$t0, ($s0) 		# create pointer
	add	$s1, $zero, $zero 	# represents n-1 of array
	la 	$a0, startMsg 
	jal	Print_string 		# print message
InputLoop: # Take in only positive integers and store them in array until user enters -1
	la 	$a0, prompt
	jal 	Print_string 		# Print prompt
	jal 	Read_integer 		# read integer
	beq	$v0, -1, isArrayEmpty 	# Exit if user enters -1
	sw	$v0, ($t0) 		# Store integer
	add	$t0, $t0, 4 		# increment pointer
	add	$s1, $s1, 1 		# increment counter
	j 	InputLoop
isArrayEmpty: # If the user only enters -1, there is nothing to sort
	bne 	$t0, $s0, arrayNotEmpty
	la	$a0, emptyMsg
	jal 	Print_string	
	jal 	Exit
arrayNotEmpty: # The array isn't empty, continue execution
	add	$t0, $s0, $zero
	add	$t1, $zero, $zero
	la	$a0, unsortedMsg
	jal 	Print_string
printLoopUnsorted:
	lw	$a0, ($t0)
	jal 	Print_integer
	la	$a0, separator
	jal 	Print_string
	add	$t0, $t0, 4
	add	$t1, $t1, 1
	bne	$s1, $t1, printLoopUnsorted

	# Call MergeSort for first time
	sub	$s1, $s1, 1		# set s1 to length-1
	add	$a0, $zero, $zero 	# low stored in $a0
	add	$a1, $zero, $zero 	# mid stored in $a1
	add	$a2, $zero, $s1		# high stored in $a2
	jal	MergeSort
			
	# Finish execution in main by printing sorted array
	add	$t0, $s0, $zero
	add	$t1, $zero, $zero
	la 	$a0, sortedMsg
	jal	Print_string
	addi	$s1, $s1, 1		# set s1 to length
printLoopSorted:
	lw	$a0, ($t0)
	jal 	Print_integer
	la	$a0, separator
	jal 	Print_string
	add	$t0, $t0, 4
	add	$t1, $t1, 1
	bne	$s1, $t1, printLoopSorted
	jal 	Exit 			# End the program
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# How it works: This mergesort algorithm does not follow the algorithm listed in the
# homework prompt. I believe it is simpler. Mergesort() takes in low and high arguments
# (the array is globally saved and accessed) and then makes recursive calls to 
# mergesort(low, mid) and then mergesort(mid+1, high) and then calls merge(low, mid, high). 
# Merge() creates L1 and L2 to look at the elements of the array. It creates a second 
# array (b) of the required size and places elements from a into b based on the 
# divide and conquer conditions passed. Once the merge is done, control is returned
# to Mergesort which continues the algorithm. For more information, visit 
# https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_program_in_c.htm

# --- MergeSort Procedure ---
MergeSort:
	addi	$sp, $sp, -16		# adjust stack, push return address
	sw	$ra, 12($sp)
	
	bge	$a0, $a2, MergeSortEnd 	# if low >= high, end procedure
	add	$a1, $zero, $zero 	# reset mid
	add	$t0, $a0, $a2 		# temp = low + high
	div 	$a1, $t0, 2		# mid = temp / 2 
	
	# push arguments onto stack
	sw	$a0, 0($sp)
	sw	$a1, 4($sp)
	sw	$a2, 8($sp)
	
	add	$a2, $a1, $zero		# Call MergeSort(low, mid)
	jal 	MergeSort
	
	# load arguments back
	lw	$a0, 0($sp)
	lw	$a1, 4($sp)
	lw	$a2, 8($sp)
	# lw	$ra, 12($sp)

	addi	$a0, $a1, 1		# Call MergeSort(mid+1, high)
	jal MergeSort
	
	# load arguments back
	lw	$a0, 0($sp)
	lw	$a1, 4($sp)
	lw	$a2, 8($sp)
	lw	$ra, 12($sp)

	jal 	Merge			# Call Merge
MergeSortEnd:
	lw	$ra, 12($sp)		# Load return address
	addi	$sp, $sp, 16 		# Readjust stack pointer
	jr	$ra			# Return
# ---------------------------

# --- Merge Procedure ---
Merge:
	add	$s2, $zero, $zero	# initialize
	add	$t3, $zero, $zero
	add	$t9, $zero, $zero
	add	$t0, $a0, $zero		# i = low
	add	$t1, $a0, $zero		# L1 = low
	addi	$t2, $a1, 1		# L2 = mid + 1
	
	add	$s2, $a0, $zero		# Protect a0 from being overwritten permanently
	add	$a0, $a2, $zero		# create array b for merging
	li	$v0, 9
	syscall

	add	$t3, $v0, $zero 	# tmp3 points to arrayb
	add	$a0, $s2, $zero
	add	$s2, $t3, $zero		# s2 points to arrayb as backup
	
While1:
	mul	$t9, $t1, 4		# tmp9 is the array index converter (turn i into address increment)
	add	$t5, $t9, $s0		# tmp5 = &a[L1]
	lw	$t5, ($t5)		# tmp5 = *a[L1]
	mul	$t9, $t2, 4
	add	$t6, $t9, $s0		# tmp6 = &a[L2]
	lw	$t6, ($t6)		# tmp6 = *a[L2]
	add	$t3, $s2, $zero		# tmp3 = &b[0]
	mul	$t9, $t0, 4
	add	$t3, $t3, $t9		# tmp3 = &b[i]
	
	bgt	$t5, $t6, Else1		# if *a[L1] <= *a[L2] then
	sw	$t5, ($t3)		# *b[i] = *a[L1]
	addi	$t1, $t1, 1		# L1 = L1 + 1
	j	Final1
Else1:					# else
	sw	$t6, ($t3)		# *b[i] = *a[L2]
	addi	$t2, $t2, 1		# L2 = L2 + 1
Final1:
	addi	$t0, $t0, 1		# i = i + 1
	bgt	$t1, $a1, End1		# loop only if L1 <= mid
	bgt	$t2, $a2, End1		# loop only if L2 <= high
	# addi	$t0, $t0, 1		# i = i + 1
	j	While1
End1:
	bgt	$t1, $a1, End2		# loop only if L1 <= mid
	
While2:
	mul	$t9, $t1, 4
	add	$t5, $t9, $s0		# tmp5 = &a[L1]
	lw	$t5, ($t5)		# tmp5 = *a[L1]
	add	$t3, $s2, $zero		# tmp3 = &b[0]
	mul	$t9, $t0, 4
	add	$t3, $t3, $t9		# tmp3 = &b[i]
	sw	$t5, ($t3)		# *b[i] = *a[L1]
	addi	$t1, $t1, 1		# L1 = L1 + 1
	addi	$t0, $t0, 1		# i = i + 1	
	bgt	$t1, $a1, End2		# loop only if L1 <= mid
	j	While2
End2:
	bgt	$t2, $a2, End3		# loop only if L2 <= high
	
While3:
	mul	$t9, $t2, 4
	add	$t6, $t9, $s0		# tmp6 = &a[L2]
	lw	$t6, ($t6)		# tmp6 = *a[L2]
	add	$t3, $s2, $zero		# tmp3 = &b[0]
	mul	$t9, $t0, 4
	add	$t3, $t3, $t9		# tmp3 = &b[i]
	sw	$t6, ($t3)		# *b[i] = *a[L2]
	addi	$t2, $t2, 1		# L2 = L2 + 1
	addi	$t0, $t0, 1		# i = i + 1
	bgt	$t2, $a2, End3		# loop only if L2 <= high
	j	While3
	
End3:
	add	$t0, $a0, $zero		# i = low
	add	$t7, $s0, $zero		# tmp7 = &a[0]
	
While4:
	add	$t3, $s2, $zero		# tmp3 = &b[0] 
	mul	$t9, $t0, 4
	add	$t3, $t3, $t9		# tmp3 = &b[i]
	lw	$t3, ($t3)		# tmp3 = *b[i]
	add	$t7, $s0, $zero		# tmp7 = &a[0]
	add	$t7, $t7, $t9		# tmp7 = &a[i]
	sw	$t3, ($t7)		# *a[i] = *b[i]
	addi	$t0, $t0, 1		# i = i + 1
	bgt	$t0, $a2, MergeEnd	# loop only if i <= high
	j	While4
	
MergeEnd:
	jr	$ra			# Return
# ---------------------------

# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
	.data
startMsg:
	.asciiz "\nPlease enter positive integers. When you are finished enter -1.\n"
prompt:
	.asciiz "Enter integer: "
emptyMsg:
	.asciiz "Nothing to sort -- the array is empty!\n"
unsortedMsg:
	.asciiz "\nUnsorted array: "
sortedMsg:
	.asciiz "\nSorted array:   "
separator:
	.asciiz " "
	
	.align 4
array1: 
	.space 60 # 60 bytes for max 15 integers
	
	.align 4
arrayL:
	.space 32 # 32 bytes for max 8 integers
	
	.align 4
arrayR:
	.space 32 # 32 bytes for max 8 integers
	
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

# Wrapper functions around some of the system calls
# From P&H COD, Fig. A.9.1
	.text

	.globl Read_integer
Read_integer: 	# input an integer to be stored in v0
	addi	$v0, $zero, 5
	syscall
	jr	$ra

	.globl Print_integer
Print_integer: # print the integer in register a0
	addi 	$v0, $zero, 1
	syscall
	jr 	$ra

	.globl	Print_string
Print_string:	# print the string whose starting address is in register a0
	addi	$v0, $zero, 4
	syscall
	jr	$ra

	.globl	Exit
Exit:		# end the program, no explicit return status
	addi	$v0, $zero, 10
	syscall
	jr	$ra

	.globl	Exit2
Exit2:		# end the program, with return status from register a0
	addi	$v0, $zero, 17
	syscall
	jr	$ra