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

July 04, 2024
Rehana Magnus
Assembly Language
Rehana Magnus, PhD in Computer Science from the esteemed Acadia Institute of Technology, Canada. With 6 years of experience, specializes in assembly language programming. Proficient in low-level coding, optimizing performance, and enhancing system functionality.
Key Topics
• Instructions
• Requirements and Specifications
Tip of the day
News

## 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
Source Code
`# Muaadh Ahmed mxa210061.datalist1: .space 128 # space to save first arraylist1array: .word 0 # first array sizelist2: .space 128 # space to save second arraylist2array: .word 0 # second array sizemergedlist: .space 128 # space for merged listlist: .word 6, 5, 9, 1, 7, 0, -3, 2 # list to sortlistsize: .word 8 # list size.text.globl mainmain: # Merge Sort the list li \$s0, 1 # len = 1 lw \$s1, listsize # n = list sizemSortLoop: bge \$s0, \$s1, printList # if len >=n, end li \$s2, 0 # i = 0while1: 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 - 1doMerge: # copy sublists move \$t0, \$s3 # j = L1 li \$t1, 0 # k = 0forL1: 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 forL1endForL1: sw \$t1, list1array # save size for list1 move \$t0, \$s5 # j = L2 li \$t1, 0 # k = 0forL2: 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 forL2endForL2: 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 = 0for1: 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 for1endFor1: sll \$t0, \$s0, 1 # 2*len add \$s2, \$s2, \$t0 # i = i + 2*len j while1endWhile1: sll \$s0, \$s0, 1 # len = 2*len j mSortLoopprintList: # print sorted array lw \$t1, listsize # list size la \$t2, list # point to start of list li \$t0, 0 # list indexlooppr: 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 elementsprintex:        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 jloop: 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 list1add1: 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_listsecond:        add \$t4, \$t4, 4 j loop# if list1 has remaining elements add them to mergeslistloop1: 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 mergedlistloop2: 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 list2loopex: jr \$ra # return to caller`

## Related Samples

Explore our Assembly Language Assignments samples to grasp foundational concepts and advanced techniques. Gain insights into memory management, bitwise operations, optimization strategies, and more. Each example is crafted to enhance your understanding and proficiency in Assembly programming. Start exploring and mastering Assembly today!