Create a Program To Merge Sort In MIPS Assembly Language Assignment Solution
July 04, 2024
Rehana Magnus
🇨🇦 Canada
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 callerRelated 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!
Assembly Language
Word Count
11673 Words
Writer Name:Dr. Denise M. Lopez
Total Orders:500
Satisfaction rate:
Assembly Language
Word Count
3655 Words
Writer Name:Dr. John L. Sanders
Total Orders:900
Satisfaction rate:
Assembly Language
Word Count
11176 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
1782 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
7747 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
2371 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
1270 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
5650 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
5768 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
1586 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
2204 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
3452 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
6803 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
5272 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
2752 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
10514 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
2587 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
15048 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
4268 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate:
Assembly Language
Word Count
4470 Words
Writer Name:Rehana Magnus
Total Orders:750
Satisfaction rate: