+1 (315) 557-6473 

Create a Program To Merge Sort In MIPS Assembly Language Assignment Solution.


Instructions

Objective
Write an MIPS assignment program to create a program to merge sort in assembly language.

Requirements and Specifications

Convert "merge" in Project 2 into a subroutine. Write a "main" program to perform merge sorting of a list of integers by calling "merge" repeatedly. For example, if the sorting program takes (6, 5, 9, 1, 7, 0, -3, 2) as input, it will produce a sorted list (-3, 0, 1,& 2, 4, 6, 7, 9).
The original unsorted list of integers should be received from the keyboard input. Your program should first ask for user to input the number of integers in the original list, and then ask for inputting all the integers. The total number of integers to be sorted by this program should be a power of 2. This means, the program should work with a list of 2, 4, 8, 16, or 32 (...) integers (but your program needs only to handle up to 32 integers).
The final sorted list (in increasing order) should be stored in the data area, that starts with the label "list:". The sorted list should also be displayed on the screen (console). You should not do this part by implementing a different sorting algorithm (e.g., quick sort). You will receive 0% if you do not make use of "merge", or if your sorted list is in decreasing order.
Screenshots of output
merge sort in MIPS assembly language
Source Code
# Muaadh Ahmed mxa210061
.data
list1: .space 128 # space to save first array
list1array: .word 0 # first array size
list2: .space 128 # space to save second array
list2array: .word 0 # second array size
mergedlist: .space 128 # space for merged list
list: .word 6, 5, 9, 1, 7, 0, -3, 2 # list to sort
listsize: .word 8 # list size
.text
.globl main
main:
 # Merge Sort the list
 li $s0, 1 # len = 1
 lw $s1, listsize # n = list size
mSortLoop:
 bge $s0, $s1, printList # if len >=n, end
 li $s2, 0 # i = 0
while1:
 bge $s2, $s1, endWhile1 # if i >=n, end while
 move $s3, $s2 # L1 = i
 add $s5, $s2, $s0 # L2 = i + len
 addi $s4, $s5, -1 # R1 = i + len - 1
 add $s6, $s5, $s0 # i + 2*len
 addi $s6, $s6, -1 # R2 = i + 2*len - 1
 bge $s5, $s1, printList # if L2 >= n, end loop
 blt $s6, $s1, doMerge # if R2 < n, go to merge
 addi $s6, $s1, -1 # else, R2 = n - 1
doMerge:
 # copy sublists
 move $t0, $s3 # j = L1
 li $t1, 0 # k = 0
forL1:
 bgt $t0, $s4, endForL1 # if j > R1, end for
 sll $t2, $t0, 2 # j *4
 lw $t3, list($t2) # load list[j]
 sll $t2, $t1, 2 # k *4
 sw $t3, list1($t2) # list1[k] = list[j]
 addi $t0, $t0, 1 # j++
 addi $t1, $t1, 1 # k++
 j forL1
endForL1:
 sw $t1, list1array # save size for list1
 move $t0, $s5 # j = L2
 li $t1, 0 # k = 0
forL2:
 bgt $t0, $s6, endForL2 # if j > R2, end for
 sll $t2, $t0, 2 # j *4
 lw $t3, list($t2) # load list[j]
 sll $t2, $t1, 2 # k *4
 sw $t3, list2($t2) # list2[k] = list[j]
 addi $t0, $t0, 1 # j++
 addi $t1, $t1, 1 # k++
 j forL2
endForL2:
 sw $t1, list2array # save size for list2
 # merge sublists
 la $a0,list1 # load first array pointer
        lw $a1,list1array # load first array size
 la $a2,list2 # load second array pointer
        lw $a3,list2array # load second array size
 la $t0, mergedlist # load merge array pointer
 addi $sp, $sp, -4 # allocate space in stack to save argument
 sw $t0, 0($sp) # save last argument in stack
 jal merge # merge lists
 addi $sp, $sp, 4 # remove allocated space from stack
 # copy merge result to initial list
 sub $t1, $s6, $s3 # R2 - L1
 addi $t1, $t1, 1 # R2 - L1 + 1
 li $t0, 0 # j = 0
for1:
 bge $t0, $t1, endFor1 # if j >= R2 - L1 + 1, end for
 sll $t2, $t0, 2 # j *4
 lw $t3, mergedlist($t2) # load mergedlist[j]
 add $t2, $t0, $s2 # i + j
 sll $t2, $t2, 2 # (i + j) *4
 sw $t3, list($t2) # list[i + j] = mergedlist[j]
 addi $t0, $t0, 1 # j++
 j for1
endFor1:
 sll $t0, $s0, 1 # 2*len
 add $s2, $s2, $t0 # i = i + 2*len
 j while1
endWhile1:
 sll $s0, $s0, 1 # len = 2*len
 j mSortLoop
printList:
 # print sorted array
 lw $t1, listsize # list size
 la $t2, list # point to start of list
 li $t0, 0 # list index
looppr:
 beq $t0, $t1, printex # if i>= n, exit loop
        lw $a0, 0($t2) # else load element from list
 li $v0, 1 # prints list element
        syscall
 li $a0, 32 # load ascii space
 li $v0, 11 # syscall to print character
        syscall
 add $t2, $t2, 4 # goes to next element in the list
 add $t0, $t0, 1 # increment index
 j looppr # repeat to print rest of elements
printex:
        li $v0, 10 # exit syscall
 syscall  
#-----------------------------------------
# Merge subroutine
#-----------------------------------------
merge:
 lw $t4, 0($sp) # load merge list pointer from stack
 li $t0, 0 # index i
 li $t1, 0 # index j
loop:
 beq $t0, $a1,loop1 # if i >= n1, exit loop
 lw $t2, 0($a0) # load element from first list
 # load second element into $a1
 beq $t1, $a3, loop1 # if j >= n2, exit the loop
 lw $t3, 0($a2) # load element from second array
 ble $t2, $t3, add1 # if arr1[i] <= arr2[j], add from first
 sw $t3, 0($t4) # else, adds from second to merge list
        add $t1, $t1, 1 # increment j second array index
        add $a2, $a2, 4 # goes to next element of list2
 j second
# merges list1
add1:
 sw $t2, 0($t4) # save from first list to merge list
 add $t0, $t0, 1 # increment i first array index
 add $a0, $a0, 4 # goes to next element of list1
#point next location in the merged_list
second:
        add $t4, $t4, 4
 j loop
# if list1 has remaining elements add them to mergeslist
loop1:
 beq $t0, $a1, loop2 # if no more elements in first list, go to second
 lw $t2, 0($a0) # load element from first list
 sw $t2, 0($t4) # save in merge list
 add $a0, $a0, 4 # advance to next element in first list
 add $t4, $t4, 4 # advance position in merge list
 add $t0, $t0, 1 # increment first list index
 j loop1 # repeat to add all elements in list1
# if list2 has remaining elements add them to mergedlist
loop2:
 beq $t1, $a1, loopex # if no more elements in second list, end
 lw $t2, 0($a2) # load element from second list
 sw $t2, 0($t4) # save in merge list
 add $a2, $a2, 4 # advance to next element in second list
 add $t4, $t4, 4 # advance position in merge list
 add $t1, $t1, 1 # increment second list index
 j loop2 # repeat to add all elements in list2
loopex:
 jr $ra # return to caller