# Experiment 2: MIPS Assembly Language Programming: Recursion

HELP NOTES

**if | S | < Q then**sort S and return the**k-th**element

else subdivide**S**into subsequences of**Q**elements each

**end if**.- You can implement any algorithm for sorting: Insertion sort, Selection sort, Bubble sort, Shell sort, Merge sort, Heapsort, Quicksort, etc. However, choose a simple implementation (e.g.: Insertion). See their description at http://www.itl.nist.gov/div897/sqg/dads/HTML/sort.html and relevant animations at http://www.sorting-algorithms.com/.
- The median for a given list of numbers is found as follows: Sort these numbers either in increasing or decreasing order, and then identify the number in the middle of this ordered sequence. If the original list has odd SIZE, then the median is the [(SIZE+1)/2]-th element in the ordered sequence. If the original list has even SIZE, then the median is the arithmetic average of the two numbers in the middle of the ordered sequence, that is: median={(value of the [SIZE/2]-th element)+ (value of the [(SIZE+2)/2]-th element)}/2.
- Sort each subsequence and determine its median. (See above discussion)

The sequence S will look like below: - Call SELECT recursively to find m, the median of the medians found in 2.
- Create three subsequences S1, S2, and S3 to contain elements of S smaller than, equal to, and larger than m, respectively.

Use any sort routine. The routine should have at least two parameters: base address of the
array and size.

**NOTES:**

**Examples:**If the sorted sequence is {S0, S1, S2, S3, S4}, then Median = S2;.

For the sorted sequence {S0, S1, S2, S3, S4, S5}, Median = (S2+S3) / 2.

For the sake of simplicity in this experiment, for the even SIZE case choose as the median the number at offset SIZE/2 of the ordered sequence.

Before you call the SELECT procedure, you had better make some data manipulations on sequence S.

Now you can call the SELECT procedure on the Sm sequence.

To create these three sequences use a temporary array S’ (NOT used between recursive calls of SELECT procedure; this array is used only inside one SELECT procedure). Copy S elements in S’ (S’ is an image of S) and then implement the procedure shown in the figure below.

4.1 **if | S1| ≥ k **then call **SELECT** recursively to find the **k-th** element of **S1**

else** if | S1| + | S2| ≥ k** then return **m**

else call **SELECT** recursively to find the **(k - | S1| - | S2|)-th** element of S3

**end if
end if.**

## Useful Links

- SPIM tutorials

http://elvis.rowan.edu/spim/spim_tut.pdf

http://www.cs.umd.edu/class/fall2001/cmsc411/projects/spim/ - How a recursive function is implemented in MIPS (spim)

ttp://www.cs.iastate.edu/~cs321/recitations/factorial.spim

http://www.cs.rutgers.edu/~ryder/415/lectures/spim/fact.s.html - Assemblers, Linkers, and the SPIM Simulator by James R. Larus

http://pages.cs.wisc.edu/~larus/HP_AppA.pdf - Sorting algorithms

http://www.itl.nist.gov/div897/sqg/dads/HTML/sort.html

http://www.sorting-algorithms.com - Other Links:

http://www.eecs.harvard.edu/~ellard/Courses/cs50-asm.pdf

http://www.inf.uni-konstanz.de/dbis/teaching/ws0304/computing-systems/download/rs-05.pdf