MIPS Functions and the

Stack Segment

$7\mathrm{.}6$ In$-$Lab Tasks

The function merge$\_$sort sorts array A recursively with the help of a second merge function.

Translate these two functions into MIPS code. Write a main function to allocate an array of $n$

elements dynamically, read the array, call merge$\_$sort and then print the sorted array.

void merge$\_$sort$($int $A[],$ int $n)\{$

if $(n>1)\{$

merge$\_$sort $($ &$A[],\frac{n}{2}$; $//$ Sort the first half

merge$\_$sort$($ &$A[\frac{n}{2}],n-\frac{n}{2}$ Sort the second half

merge $($&$A[],n)$; $//$ Merge the two halves

$\}$

$\}$

$//$ merge the first $\frac{n}{2}$ elements with the last $(n-\frac{n}{2})$ elements

$//$ merge is a leaf function that makes no function calls

void merge$($int $A[],$ int $n)\{$

int $B[n]$; $//$ Allocated on the stack

int $i=0,j=\frac{n}{2},k=0$;

while $((A[i]A[j])\{B[k++]=A[i++]$;$\}\{B[k++]=A[j++]$;$\}(k=0$;$k$

$\}$