Question

Can you think of a way to perform MSD Radix Sort? (Assignment 3-Question 3 Develop'an algorithm to perform Radix Sort with MSD.)

Answer 1

MSD radix sort algorithm:--------
A recursively subdividing MSD radix sort algorithm works as follows:

• Take the most significant digit of each key.
• Sort the list of elements based on that digit, grouping elements with the same digit into one bucket.
• Recursively sort each bucket, starting with the next digit to the right.
• Concatenate the buckets together in order.

Recursive forward radix sort example.
Sort the list:
160, 022, 070, 092, 001, 044, 602, 056

Sorting by most significant digit (100s place) gives:
Zero hundreds bucket: 022, 070, 092, 001, 044, 056
One hundreds bucket: 160
Eight hundreds bucket: 602
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):
Zero tens bucket: 001
Twenties bucket: 022
Forties bucket: 044
Sixties bucket: 056
Seventies bucket: 070
Nineties bucket: 092
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 hundreds bucket is concatenated, joined in sequence, with the one hundreds bucket and eight hundreds bucket to give:
001, 022, 044, 056, 070, 092, 160, 602