There has been an answer for this question before but it was wrong. It was used
ID: 3682856 • Letter: T
Question
There has been an answer for this question before but it was wrong. It was used with a different algorithm and needs to be used with the algorithm above
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. There has been an answer for this question before but it was wrong. It was used with a different algorithm and needs to be used with the algorithm above.
Explanation / Answer
These 2 methods of approachings will help you to do this.
(i) Recursive merge sort in MIPS using stack
.data
Array1 : .word 0:20
Array2 : .word 0:20
.text
.globl main
main :
#initial activation record ... send the three arguments to sort......0
li $v0, 5 # system call for read_int
syscall
move $t4, $v0 # number read is put in $t0
li $v0, 5 # system call for read_int
syscall
move $t5, $v0 # number read is put in $t1
li $v0, 5 # system call for read_int
syscall
move $t6, $v0 # number read is put in $t2
li $v0, 5 # system call for read_int
syscall
move $t7, $v0 # number read is put in $t3
#do the syscall for array 1 and array 2(empty)(no syscall) and size save them in t0 , t1 , t2 respectively which are then send to stack
la $t0 , Array1
sw $t4 , 0($t0)
sw $t5 , 4($t0)
sw $t6 , 8($t0)
sw $t7 , 12($t0)
la $t1 , Array2
li $t2 , 4
sw $t0, -12($sp)
sw $t1, -8($sp)
sw $t2, -4($sp)
addi $sp, $sp, -184
jal sort
#.........display the result stored in B and then clear the stack (exit the program) ...........#
li $v0, 10 # system call for exit
syscall
#....................................................................0
#creating the initial activation record .............1
sort:
# a0 mein A (initial one) and a1 mein B (initial one) a2 mein initial n which will be taken as system call
sw $ra, 168($sp)
#//already done addi $sp , $sp , -184
#for n1 and n2
lw $t2 , 180($sp) #($t2 = n)
srl $t0 , $t2 , 1 #($t0 = n1 = n/2)
sra $t0 , $t2 , 1
sub $t1 , $t2 , $t0 #($t1 = n2 = n - n1)
sw $t1 , 164($sp) #(stored n2)
sw $t0 , 160($sp) #(stored n1)
#la $t0 , Array1
#la $t1 , Array2
#sw $t1 , 80($sp) #stored ARRAY2
#sw $t0 , 0($sp) #stored ARRAY1
#....................................................1
#SORT FUNC FIRST PART................................2
#ASSUMPTIONS:
#a0 = A
#a1 = B
#a2 = n
#BASE CASE
li $t0 , 1 #t0 = 1
bne $t0 , $t2 , firstL #((t2 = n) != 1) then go to firstL
lw $t1 , 172($sp) #t1 = &A
lw $t1 , 0($t1) #t1 = A[0]
lw $t2 , 176($sp) #t2 = &B
sw $t1 , 0($t2) #B[0] = A[0]
addi $sp , $sp , 184 #THE CORRECTION
jr $ra
#First Loop
firstL :
#........................................................2
#CALLING SORT ...........................................3
lw $t8, 172($sp) #loading &A
sw $t8, -12($sp) #storing &A at the desired location
add $t8, $sp, $zero #loading &A1
sw $t8, -8($sp) #storing &A1 at the desired location
lw $t8, 160($sp) #loading n1
sw $t8, -4($sp) #storing n1 at the desired location
addi $sp, $sp, -184
jal sort
#.........................................................3
#CALLING SORT AGAIN ......................................4
lw $t8, 172($sp) #loading &A
lw $t7, 160($sp) #loading n1
sll $t7 , $t7 , 2 #n1*= 4 for mips address
add $t8 , $t8 , $t7 #adding &A + n1
sw $t8, -12($sp) #storing &A + n1
addi $t8, $sp, 80 #loading &A2
sw $t8, -8($sp) #storing A2
lw $t8, 164($sp) #loading n2
sw $t8, -4($sp)
addi $sp, $sp, -184
jal sort
#calling merge...........................................5
add $a0, $sp, $zero #a0 = &A1
addi $a1, $sp, 80 #a1 = &A2
lw $a2, 176($sp) #a2 = &B
lw $t8, 160($sp)
sw $t8, -8($sp) #stored p
lw $t8, 164($sp)
sw $t8, -4($sp) #stored q
addi $sp, $sp, -12
jal merge
#........................................................5
#return from sort........................................8
lw $ra, 168($sp)
lw $t0 , 176($sp)
lw $t1 , 0($t0)
lw $t2 , 4($t0)
lw $t3 , 8($t0)
lw $t4 , 12($t0)
li $v0, 1 # system call for print_int
move $a0, $t1 # number in $t3 is to be printed
syscall
li $v0, 1 # system call for print_int
move $a0, $t2 # number in $t3 is to be printed
syscall
li $v0, 1 # system call for print_int
move $a0, $t3 # number in $t3 is to be printed
syscall
li $v0, 1 # system call for print_int
move $a0, $t4 # number in $t3 is to be printed
syscall
addi $sp , $sp , 184
jr $ra
#........................................................8
#Merge ..................................................6
merge:
sw $ra, 0($sp) #stored ra .........
#ASSUMPTION :
#a0 = P #available from stack though.....
#a1 = Q
#a2 = R
#s1 = p
#s2 = q
lw $s1 , 4($sp)
lw $s2 , 8($sp)
move $t0 , $zero # t0 = i , t1 = j, t2 = k (= 0)
move $t1 , $zero
move $t2 , $zero
While1:
sll $t3 , $t0 , 2
add $t3 , $t3 , $a0 #t3 = &P[i]
sll $t4 , $t1 , 2
add $t4 , $t4 , $a1 #t4 = &Q[j]
lw $t5 , 0($t3) #t5 = P[i]
lw $t6 , 0($t4) #t6 = Q[j]
sll $t7 , $t2 , 2
add $t7 , $t7 , $a2 #t7 = &R[k]
bge $t0 , $s1 , While2
bge $t1 , $s2 , While2 # exit loop 1 if j>=q or i>=p
bge $t5 , $t6 , While12
sw $t5 , 0($t7) #R[k] = P[i]
addi $t0 , $t0 , 1 #incremented i and k
addi $t2 , $t2 , 1
j While1
While12:
sw $t6 , 0($t7) #R[K] = Q[j]
addi $t1 , $t1 , 1 #incremented j and k
addi $t2 , $t2 , 1
j While1
While2:
bge $t0 , $s1 , While3 #exit loop if i >= p
sw $t5 , 0($t7) #R[k] = P[i]
addi $t0 , $t0 , 1 #incremented i and k
addi $t2 , $t2 , 1
j While1
While3:
bge $t1 , $s2 , Exit #exit loop if j>= q
sw $t6 , 0($t7) #R[k] = Q[j]
addi $t1 , $t1 , 1 #incremented j and k
addi $t2 , $t2 , 1
j While1
Exit :
#.........................................................6
#return from merge........................................7
lw $ra, 0($sp)
addi $sp, $sp, 12
jr $ra
#..........................................................7
#....................... END ..................................#
(ii) Merge Sort Program using an Indirect Array in MIPS Assembly
.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 " "
# 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
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.