Project 1: Merge Sort Objective: In this project, you are expected to implement
ID: 3864968 • Letter: P
Question
Project 1: Merge Sort
Objective:
In this project, you are expected to implement a merge sort algorithm in MIPS assembly language. A C++ implementation for merge sort is as follows.
int c[100]; //c[100] is a global array
mergesort(int a[], int low, int high){
int mid;
if (low < high) { mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid); }
return; }
void merge(int a[], int low, int high, int mid){
int i, j, k;
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high){
if (a[i] < a[j]){
c[k] = a[i];
k++;
i++; }
else{
c[k] = a[j];
k++;
j++; } }
while (i <= mid){
c[k] = a[i];
k++;
i++; }
while (j <= high){
c[k] = a[j];
k++;
j++; }
for (i = low; i < k; i++){
a[i] = c[i]; }
}
Problem 1:
Consider the array [1,4,7,10,25,3,5,13,17,21]. The first and second halves of this array are both already sorted. In this case, the “merge sort” over this array is reduced to the “merge” of two sorted arrays: [1,4,7,10,25] and [3,5,13,17,21]. Implement the merge function (from the C++ code above) in assembly to sort this array.
Problem 2:
Given an array [56,3,46,47,34,12,1,5,10,8,33,25,29,31,50,43], implement the complete merge sort algorithm to sort this array.
Requirements:
1. You are required to implement merge sort in a separate procedures instead of in the main function.
2. The algorithm of your assembly program should be exact the same as the one of this C++ implementation.
3. You are required to implement the MIPS program in SPIM simulator.
4. Your program should be able to display the sorted array as the output. Please refer to SPIM syscall documentation on Blackboard to see how to display messages on screen.
Hints:
1. The code snippet below demonstrates how to define a single variable, an initialized array and an empty array in the .text segment.
# Define a variable, whose name is “Var”, type is “.word” and initial value is 12 Var .word 12
# Define an array, whose name is “Array”.
# The type of each array element is “.word”.
# The array is initialized to hold 5 elements: 3, 4, 6, 10, 2 Array .word 3,4,6,10,2
# Define an array, whose name is “Array”.
# The type of each array element is “.word”.
# The array has 16 elements, each of which is initialized to be “0”. Array .word 0:16
Explanation / Answer
.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 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 " "
# 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
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.