Created
September 19, 2013 22:09
-
-
Save jmc734/6630563 to your computer and use it in GitHub Desktop.
Merge Sorting an Indirect Array in MIPS Assembly
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
.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 |
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.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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?