Instructions
Objective
Write a program to create a program to merge sort in MIPS 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