Part A of OPTION 2: Radix-Sort

The purpose of Part A is to implement a radix-sort based algorithm for sorting 32-bit unsigned integers. A 32-bit unsigned integer can be viewed as an 1-digit radix-232 − 1 integer, or a 2-digit radix-65536 integer, or a 4-digit radix-256 integer. For JAVA implementations one may assume that the input is a 31-bit non-negative integer.

void rdx_sort (unsigned int *keys, int n,

rdx_sort (int[] keys, int n,

keys

n

mradix

unsigned int mradix);

unsigned int mradix);

// C or C++

// Java

: is a pointer to the input array of unsigned int data type.

: is the dimension (number of elements) of the array.

: is the radix that will be used; each integer is viewed ad d-digit radix-mradix integer.

1. If mradix = 256, your algorithm should behave like a RadixSort algorithm and view the integers as 4-digit radix-256 numbers,

2. otherwise, if mradix = 65536, your algorithm should behave like a RadixSort algorithm and view the integers as 2-digit radix-65536 numbers,

3. otherwise, if n ≥ mradix , your algorithm should behave like CountSort,

4. otherwise, if n < mradix , then your algorithm should automatically decide the radix between radix-256 and radix-65536 and revert to a radix-sort based algorithm (i.e. choose between (1) and (2)).

Remark. Note the order of the if-otherwise statement above. If n = 10000 and mradix = 256, case 1 applies, even if case 3 is also applicable.

**Subject Computer Science C-Family Programming**