ECE Undergraduate Laboratories
ECE 459 - Advanced Computer System Design Laboratory

Experiment 2: MIPS Assembly Language Programming: Recursion

  1. if | S | < Q then sort S and return the k-th element
    else subdivide S into Number of Sequencessubsequences of Q elements each
    end if.
  2. Use any sort routine. The routine should have at least two parameters: base address of the array and size.


    1. Number of seq gen. is the number of subsequences generated. You must round up the result of the division | S | / Q. For example, if | S | =22 and Q=5 the number of subsequences will be Number of subsequences, where ⌈ • ⌉ is the ceiling operator.

    2. 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 and relevant animations at

    3. 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.

    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.

  3. Sort each subsequence and determine its median. (See above discussion)
    The sequence S will look like below:

  4. Sequence

  5. Call SELECT recursively to find m, the median of the Number of Sequences medians found in 2.

  6. 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.

  7. Create three subsequences S1, S2, and S3 to contain elements of S smaller than, equal to, and larger than m, respectively.

  8. 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

  1. SPIM tutorials

  2. How a recursive function is implemented in MIPS (spim)

  3. Assemblers, Linkers, and the SPIM Simulator by James R. Larus

  4. Sorting algorithms

  5. Other Links: