gistfile1.txt

#
# FILE:         $File$
# AUTHOR:       Phil White, RIT 2016
# CONTRIBUTORS:
#		W. Carithers
#		<<<YOUR NAME HERE>>>
#
# DESCRIPTION:
#	This program is an implementation of merge sort in MIPS
#	assembly 
#
# ARGUMENTS:
#	None
#
# INPUT:
# 	The numbers to be sorted.  The user will enter a 9999 to
#	represent the end of the data
#
# OUTPUT:
#	A "before" line with the numbers in the order they were
#	entered, and an "after" line with the same numbers sorted.
#
# REVISION HISTORY:
#	Aug  08		- P. White, original version
#

#-------------------------------

#
# Numeric Constants
#

PRINT_STRING = 4
PRINT_INT = 1

#-------------------------------

#

# ********** BEGIN STUDENT CODE BLOCK 1 **********

#
# Make sure to add any .globl that you need here
#


# Name:         sort
# Description:  sorts an array of integers using the merge sort
#		algorithm
# 		Arguments Note: a1 and a2 specify the range inclusively
#
# Arguments:    a0:     a parameter block containing 3 values
#                       - the address of the array to sort
#                       - the address of the scrap array needed by merge
#                       - the address of the compare function to use
#                         when ordering data
#               a1:     the index of the first element in the range to sort
#               a2:     the index of the last element in the range to sort
# Returns:      none
#
.globl          sort
.globl          merge

sort:
        addi	$sp,$sp,-40	# allocate space for the return address
        sw	$ra,4($sp)
        sw	$s0,8($sp)
        sw	$s1,12($sp)
        sw	$s2,16($sp)
        sw	$s3,20($sp)
        sw	$s4,24($sp)
        sw	$s5,28($sp)
        sw	$s6,32($sp)
        sw	$s7,36($sp)
        
        move    $s1, $a1      # store param a1
        move    $s2, $a2      # store param a2

        slt     $t5,$a2,$a1
        beq     $a2,$a1,sort_done
        beq     $t5,$zero,sort_non_trivial
        j       sort_done

sort_non_trivial:
        # sort left first:
        div     $a2, $s0
        mflo    $a2
        jal     sort
        
        # sort right 
        sub     $t1, $a2 ,$a1
        div     $t1, $t1 ,2
        mflo    $t1
        addi    $t1, $t1,1
        add     $t1, $t1,$a1
        move    $a1 ,$t1   # a1 now = a2 

        jal     sort


        move    $a1, $s1
        move    $a2, $s2

        sub     $t1, $a2 ,$a1
        div     $t1, $t1, 2
        mflo    $t1
        move    $a3, $t1
        jal     merge
        




sort_done:

        lw	$s7,36($sp)
        lw	$s6,32($sp)
        lw	$s5,28($sp)
        lw	$s4,24($sp)
        lw	$s3,20($sp)
        lw	$s2,16($sp)
        lw	$s1,12($sp)
        lw	$s0,8($sp)
        lw	$ra,4($sp)
        addi	$sp,$sp,40	# allocate space for the return address

        jr $ra

# ********** END STUDENT CODE BLOCK 1 **********

#
# End of Merge sort routine.
#