ECE 15B Spring 2011University of California, Santa BarbaraECE 15B Computer OrganizationProject #2: Radix Sort Due at 11:00 PM May 20th, 20111. IntroductionIn this project you are asked to implement radix sort using MIPS assembly code. In particular we will consider a particular flavor of such algorithm – using the least significant digit radix sort with counting pass on each digit. Note that this project involves understanding of arrays and pointers. These concepts were already introduced in our class, e.g., in the context of data flow instructions. Another, more elegant implementation of radix sort is based on linked lists which will be covered in depth in the second part of the course.Suppose that initially you are given array (“array”) with unsorted unsigned numbers (keys), e.g. 4-bit number array shown on Figure 1. During the first pass, keys in the array are grouped based on the least significant digit, e.g. for radix 2 keys are grouped by looking only at last bit, for radix 4 looking at 2 bits etc. During the second pass keys are grouped again using the last but one least significant digit (i.e. next bit for radix 2), but otherwise keeping the original order of keys. This operation is continued until keys are grouped for all digits with the final result being the sorted array. To implement sorting for any single step on figures 1 and 2 counting sort is performed. In the first phase the number of occurrences for each digit at the corresponding position is counted and stored in the dedicated array “count”. Then using count array the absolute position for each group of digits within array (“abspos”) is calculated. Finally, in the last phase, keys are placed into temporary array (“arraytemp”) at the locations specified by corresponding values of abspos with the values of abspos being incremented after each use. For example, let’s assume that first step of radix-2 sorting of 4-bit numbers is being performed and the key value to be sorted is “1001”. The least significant digit is “1” so that program looks into abspos[1] value. Let’s assume that current value of abspos[1] = 4. So the program will execute arraytemp[4] = “1001” and then increment abspos[1]=abspos[1]+1. The full C code of the algorithm is presented below. 2. Project TasksYour code should be written as a procedure which works for different radixes and different word width. Assume that the base and the size of the array to be sorted are passed in registers $a0, and $a1, correspondingly, while the logarithm base 2 of the radix is in $a2 and the word width in $a3. Your code has to preserve (spill) registers if necessary according to the standard rules for procedures but not the initial array. The sorted array should replace the initial one. You may create your own test array to test your code or use skeleton code. 3. Turn-in Once your code is completed and works correctly place your procedure inside skeleton code “sort.s” (which can be downloaded from the class website), name your file as lastname_sort.s (e.g. Britney Spears would have to name her files as spears_sort.s) and mail it to : [email protected] 1 of 3Initial array Step 1 Step 2 Step 3 Step 4_____________________________________________________________________________________array[0] 0011 1110 0000 0000 0000array[1] 0101 0000 0101 1001 0010array[2] 1001 0010 1001 0010 0011array[3] 1110 0011 1110 0011 0011array[4] 0011 0101 0010 0011 0101array[5] 0000 1001 0011 0101 1001array[6] 0010 0011 0011 1110 1110_____________________________________________________________________________________phase 1: count[0] = 3 count[0] = 3 count[0] = 5 count[0] = 5count[1] = 4 count[1] = 4 count[1] = 2 count[0] = 2phase 2: abspos[0] = 0 abspos[0] = 0 abspos[0] = 0 abspos[0] = 0abspos[1] = 3 abspos[1] = 3 abspos[1] = 5 abspos[0] = 2Figure 1. Example of least significant digit radix-2 sort with counting passes for 4-bit numbers. Initial array Step 1 Step 2____________________________________________array[0] 0011 0000 0000array[1] 0101 0101 0010array[2] 1001 1001 0011array[3] 1110 1110 0011array[4] 0011 0010 0101array[5] 0000 0011 1001array[6] 0010 0011 1110____________________________________________phase 1: count[0] = 1 count[0] = 4count[1] = 2 count[1] = 1count[2] = 2 count[2] = 1count[3] = 2 count[3] = 1phase 2: abspos[0] = 0 abspos[0] = 0abspos[1] = 1 abspos[1] = 4abspos[2] = 3 abspos[2] = 5abspos[3] = 5 abspos[3] = 6Figure 2. Example of least significant digit radix-4 sort with counting passes for 4-bit numbers. Page 2 of 34. Radix sort C pseudocode example#define N 1000; #define logradix 1;#define wordwidth 32;……..unsigned int array[N];unsigned int arraytemp[N];int count[logradix];int asbpos[logradix];int i, j, k;radixmask = 2^logradix -1;for(j=0; j<wordwidth; j++) { /* phase 1: counting */ for (i=0; i < N; i++) { for (k=0; k<logradix; k++) count[k] = 0; /* initialize values of count array to zero */ for (k=0; k < N; k++) count[(array[i]>>logradix)&&radixmask] ++; /* count number of times each digit occur */ } /* phase 2: calculating absolute position for each digit */ for (i=0; i < logradix; i++) { for (k=0; k<logradix; k++) abspos[k] = 0; /* initialize values of abspos array to zero */ for (k=0; k<logradix-1; k++) abspos[k+1]=abspos[k] +count[k]; /* calculate absolute position */ } /* phase 3: sorting phase */ for (i=0; i < N; i++) { curradix = (array[i]>>logradix)&&radixmask; arraytemp[abspos[curadix++]] = array[i]; /* place into arraytemp to the corresponding position */ } / * copy arraytemp to array (this step could be avoided but added for simplicity) */ for (i=0; i < N; i++) { array[i] = (array[i]>>logradix)&&radixmask; arraytemp[abspos[curadix++]] = array[i]; }} Page 3 of