# 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
