Merge Sorting an Indirect Array in MIPS Assembly

mergesort.asm

	.text

	la	$a0, info		# Load the start address of the array
	lw	$t0, length		# Load the array length
	sll	$t0, $t0, 2		# Multiple the array length by 4 (the size of the elements)
	add	$a1, $a0, $t0		# Calculate the array end address
	jal	mergesort		# Call the merge sort function
  	b	sortend			# We are finished sorting
	
##
# Recrusive mergesort function
#
# @param $a0 first address of the array
# @param $a1 last address of the array
##
mergesort:

	addi	$sp, $sp, -16		# Adjust stack pointer
	sw	$ra, 0($sp)		# Store the return address on the stack
	sw	$a0, 4($sp)		# Store the array start address on the stack
	sw	$a1, 8($sp)		# Store the array end address on the stack
	
	sub 	$t0, $a1, $a0		# Calculate the difference between the start and end address (i.e. number of elements * 4)

	ble	$t0, 4, mergesortend	# If the array only contains a single element, just return
	
	srl	$t0, $t0, 3		# Divide the array size by 8 to half the number of elements (shift right 3 bits)
	sll	$t0, $t0, 2		# Multiple that number by 4 to get half of the array size (shift left 2 bits)
	add	$a1, $a0, $t0		# Calculate the midpoint address of the array
	sw	$a1, 12($sp)		# Store the array midpoint address on the stack
	
	jal	mergesort		# Call recursively on the first half of the array
	
	lw	$a0, 12($sp)		# Load the midpoint address of the array from the stack
	lw	$a1, 8($sp)		# Load the end address of the array from the stack
	
	jal	mergesort		# Call recursively on the second half of the array
	
	lw	$a0, 4($sp)		# Load the array start address from the stack
	lw	$a1, 12($sp)		# Load the array midpoint address from the stack
	lw	$a2, 8($sp)		# Load the array end address from the stack
	
	jal	merge			# Merge the two array halves
	
mergesortend:				

	lw	$ra, 0($sp)		# Load the return address from the stack
	addi	$sp, $sp, 16		# Adjust the stack pointer
	jr	$ra			# Return 
	
##
# Merge two sorted, adjacent arrays into one, in-place
#
# @param $a0 First address of first array
# @param $a1 First address of second array
# @param $a2 Last address of second array
##
merge:
	addi	$sp, $sp, -16		# Adjust the stack pointer
	sw	$ra, 0($sp)		# Store the return address on the stack
	sw	$a0, 4($sp)		# Store the start address on the stack
	sw	$a1, 8($sp)		# Store the midpoint address on the stack
	sw	$a2, 12($sp)		# Store the end address on the stack
	
	move	$s0, $a0		# Create a working copy of the first half address
	move	$s1, $a1		# Create a working copy of the second half address
	
mergeloop:

	lw	$t0, 0($s0)		# Load the first half position pointer
	lw	$t1, 0($s1)		# Load the second half position pointer
	lw	$t0, 0($t0)		# Load the first half position value
	lw	$t1, 0($t1)		# Load the second half position value
	
	bgt	$t1, $t0, noshift	# If the lower value is already first, don't shift
	
	move	$a0, $s1		# Load the argument for the element to move
	move	$a1, $s0		# Load the argument for the address to move it to
	jal	shift			# Shift the element to the new position 
	
	addi	$s1, $s1, 4		# Increment the second half index
noshift:
	addi	$s0, $s0, 4		# Increment the first half index
	
	lw	$a2, 12($sp)		# Reload the end address
	bge	$s0, $a2, mergeloopend	# End the loop when both halves are empty
	bge	$s1, $a2, mergeloopend	# End the loop when both halves are empty
	b	mergeloop
	
mergeloopend:
	
	lw	$ra, 0($sp)		# Load the return address
	addi	$sp, $sp, 16		# Adjust the stack pointer
	jr 	$ra			# Return

##
# Shift an array element to another position, at a lower address
#
# @param $a0 address of element to shift
# @param $a1 destination address of element
##
shift:
	li	$t0, 10
	ble	$a0, $a1, shiftend	# If we are at the location, stop shifting
	addi	$t6, $a0, -4		# Find the previous address in the array
	lw	$t7, 0($a0)		# Get the current pointer
	lw	$t8, 0($t6)		# Get the previous pointer
	sw	$t7, 0($t6)		# Save the current pointer to the previous address
	sw	$t8, 0($a0)		# Save the previous pointer to the current address
	move	$a0, $t6		# Shift the current position back
	b 	shift			# Loop again
shiftend:
	jr	$ra			# Return
	
sortend:				# Point to jump to when sorting is complete


# Print out the indirect array
	li	$t0, 0				# Initialize the current index
prloop:
	lw	$t1,length			# Load the array length
	bge	$t0,$t1,prdone			# If we hit the end of the array, we are done
	sll	$t2,$t0,2			# Multiply the index by 4 (2^2)
	lw	$t3,info($t2)			# Get the pointer
	lw	$a0,0($t3)			# Get the value pointed to and store it for printing
	li	$v0,1				
	syscall					# Print the value
	la	$a0,eol				# Set the value to print to the newline
	li	$v0,4				
	syscall					# Print the value
	addi	$t0,$t0,1			# Increment the current index
	b	prloop				# Run through the print block again
prdone:						# We are finished
	li	$v0,10
	syscall
	.data
eol:	.asciiz	"\n"


# Some test data
eight:	.word	8
five:	.word	5
four:	.word	4
nine:	.word	9
one:	.word	1
seven:	.word	7
six:	.word	6
ten:	.word	10
three:	.word	3
two:	.word	2

# An array of pointers (indirect array)
length:	.word	10	# Array length
info:	.word	seven
	.word	three
	.word	ten
	.word	one
	.word	five
	.word	two
	.word	nine
	.word	eight
	.word	four
	.word	six

Hi,

I'm trying to implement your code of mergesort. I'm wondering how you could do this by taking user input and storing that into the array, rather than declaring the numbers?

It might be waaaaay to late to answer this question but I'll still answer it in case someone lands here and has the same question. There is a system call to read integers.

li $v0, 5 # 5 being the opcode to read integer
syscall
move $s0, $v0 # store the value read into register $s0

You can find all the available syscall on the internet pretty easily, namely here.