*IN MIPS programming language* Convert \"merge\" in Assignment 3 into a subrouti
ID: 3812861 • Letter: #
Question
*IN MIPS programming language* Convert "merge" in Assignment 3 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 the 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.
Explanation / Answer
MERGE SORT:
Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being (n log n), it is one of the most respected algorithms. Merge sort first divides the array into equal halves and then combines them in a sorted manner.
Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.
To sort A[p .. r]:
1. Divide Step
If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].
2. Conquer Step
Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].
3. Combine Step
Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).
Algorithm: Merge Sort
Merge sort keeps on dividing the list into equal halves until it can no more be divided. By definition, if it is only one element in the list, it is sorted. Then, merge sort combines the smaller sorted lists keeping the new list sorted too.
Step 1 if it is only one element in the list it is already sorted, return.
Step 2 divide the list recursively into two halves until it can no more be divided.
Step 3 merge the smaller lists into new list in sorted order.
To sort the entire sequence A[1 .. n], make the initial call to the procedure MERGE-SORT (A, 1, n).
MERGE-SORT (A, p, r)
1. IF p < r // Check for base case
2. THEN q = FLOOR[(p + r)/2] // Divide step
3. MERGE (A, p, q) // Conquer step.
4. MERGE (A, q + 1, r) // Conquer step.
5. MERGE (A, p, q, r) // Conquer step.
MERGE procedure is as follow:
MERGE (A, p, q, r )
1. n1 q p + 1
2. n2 r q
3. Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4. FOR i 1 TO n1
5. DO L[i] A[p + i 1]
6. FOR j 1 TO n2
7. DO R[j] A[q + j ]
8. L[n1 + 1]
9. R[n2 + 1]
10. i 1
11. j 1
12. FOR k p TO r
13. DO IF L[i ] R[ j]
14. THEN A[k] L[i]
15. i i + 1
16. ELSE A[k] R[j]
17. j j + 1
Code:
procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
return c
end procedure
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.