# 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
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 = 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 - 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 ```