1. There is MSD radix sort algorithm. From Wikipedia: A most significant digit (MSD) radix sort can be used to sort keys in lexicographic order. Unlike a least significant digit (LSD) radix sort, a most significant digit radix sort does not necessarily preserve the original order of duplicate keys. An MSD radix sort starts processing the keys from the most significant digit, leftmost digit, to the least significant digit, rightmost digit. This sequence is opposite that of least significant digit (LSD) radix sorts. An MSD radix sort stops rearranging the position of a key when the processing reaches a unique prefix of the key. Some MSD radix sorts use one level of buckets in which to group the keys.

2. A given algorithm from Wikipedia that represents part 2 is:

a. A recursively subdividing MSD radix sort algorithm works as follows:

i. Take the most significant digit of each key.

ii. Sort the list of elements based on that digit, grouping elements with the same digit into one bucket.

iii. Recursively sort each bucket, starting with the next digit to the right. iv. Concatenate the buckets together in order. b. Recursive forward radix sort example Sort the list: 170, 045, 075, 090, 002, 024, 802, 066 c. Sorting by a most significant digit (100s place) gives i. Zero hundreds bucket: 045, 075, 090, 002, 024, 066 ii. One hundreds bucket: 170 iii. Eight hundreds bucket: 802 d. Sorting by next digit (10s place) is only needed for those numbers in the zero hundreds bucket (no other buckets contain more than one item):

i. Zero tens bucket: 002

ii. Twenties bucket: 024

iii. Forties bucket: 045

iv. Sixties bucket: 066

v. Seventies bucket: 075

vi. Nineties bucket: 090 e. Sorting by least significant digit (1s place) is not needed, as there is no tens bucket with more than one number. Therefore, the now sorted zero hundred buckets is concatenated, joined in sequence, with the one hundred buckets and eight hundred buckets to give: 002, 024, 045, 066, 075, 090, 170, 802

3. Solve the example given by figure 8.3 using the methods from 1 and 2.

4. Solve Using Figure 8.3 as a model, illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX. using the methods presented by 1 and 2.

performed by a card sorter is stabl changing the order of the cards as th in a bin have the same digit in the cl Chapter 8 Sorting in Linear Time 329 457 657 839 ...]i. 457 . 436 720 355 720 355 436 720 329 436 839 355 457 657 329 355 436 i. 457 657 720 839 657 329 839 Figure 8.3 The operation of radix sort on a the input. The remaining columns show the lis positions. Shading indicates the digit position performed by a card sorter is stabl changing the order of the cards as th in a bin have the same digit in the cl Chapter 8 Sorting in Linear Time 329 457 657 839 ...]i. 457 . 436 720 355 720 355 436 720 329 436 839 355 457 657 329 355 436 i. 457 657 720 839 657 329 839 Figure 8.3 The operation of radix sort on a the input. The remaining columns show the lis positions. Shading indicates the digit position