Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Homework #8 Computer Organization
Homework #8 Learning Objectives:
After homework #8, you should be able to:
· write a MIPS assembly-language program with subprograms that use the MIPS register conventions
Write a MIPS assembly language program to merge sort an array of integers. The general idea of merge sort is as follows. Assume “n” items to sort.
You “just” need to translate the following C++ merge sort and merge code to MIPS assembly language. HOWEVER, YOU NEED TO FOLLOW THE MIPS REGISTER CONVENTIONS.
void mergeSort(int myArray[], int size) {
int index;
if (size > 1) { // For array size of 0 or 1, nothing to do since it’s already sorted
// Determine size of each half
int leftSize = size / 2; // NOTE: Use the MIPS “srl $##,$## ,1”
int rightSize = size - leftSize;
// Dynamically allocate arrays big enough to hold each half
int * leftArray = new int [leftSize]; // NOTE: Use the sbrk syscall
int * rightArray = new int [rightSize]; // NOTE: Use the sbrk syscall
// Copy each half to their arrays
for (index = 0; index < leftSize; index++) {
leftArray[index] = myArray[index];
} // end for
for (index = 0; index < rightSize; index++) {
rightArray[index] = myArray[leftSize+index];
} // end for
// Recursively sort both halves
mergeSort(leftArray, leftSize);
mergeSort(rightArray, rightSize);
// Merge sorted halves back together to complete the sort
merge(myArray, size, leftArray, leftSize, rightArray, rightSize);
// Deallocate (“Free up”) memory from both array halves
delete [] leftArray; // NOTE: no good syscall so we’ll waste some memory
delete [] rightArray;
} // end if
} // end mergeSort
NOTE: merge has more than 4 arguments, so the last two arguments will need to be pushed on the run-time stack by mergeSort before it calls merge. When merge starts running, it can pop these values from the stack.
void merge(int sortedArray[], int size, int leftArray[], int leftSize,
int rightArray[], int rightSize) {
int left = 0;
int right = 0;
int next = 0;
// Repeatedly copy the next smaller element from either the leftArray or rightArray
// to the end of the combined sortedArray until one of the smaller arrays runs out of
// elements.
while (left < leftSize && right < rightSize) { // NOTE: “&&” means Boolean “AND”
if (leftArray[left] < rightArray[right]) {
sortedArray[next] = leftArray[left];
left++;
} else {
sortedArray[next] = rightArray[right];
right++;
} // end if
next++;
} // end while
// Copy the remain elements from the leftArray if the rightArray ran out first
while (left < leftSize) {
sortedArray[next] = leftArray[left];
left++;
next++;
} // end while
// Copy the remain elements from the rightArray if the leftArray ran out first
while (right < rightSize) {
sortedArray[next] = rightArray[right];
right++;
next++;
} // end while
} // end merge
Run your program on the following array values: 6010 3510 1010 5010 4510 2010 2510 4510 3010.
Your program should be in a single file hw8.s organized like:
.data
array: .word 60 35 10 50 45 20 25 45 30
n: .word 9
.text
.globl main
main:
# call to mergeSort here
li $v0, 10 # system call to exit the program
syscall
mergeSort:
# mergeSort subprogram here
jr $ra
merge:
# merge subprogram here
jr $ra
You need to submit two files on eLearning at the Homework #8 Submission Link:
· the MIPS assembly language program hw8.s
· a “snip” screen capture of the simulator after running your assembly language program with the array values: 60 35 10 50 45 20 25 45 30. Make sure the sorted array is visible in the data section tab of the screen capture.