It is a non-comparative integer sorting algorithm. It sorts data by grouping keys by the individual digits which share the same significant position and value. Think Tens, Hundreds, Thousands etc. Some pointers about Radix Sort:
- Even though it is an integer sorting algorithm, it is not restricted just to integers. Integers can also represent strings of characters
- Two types of radix sort are:
- LSD (Least Significant Digit): Short keys come before long keys
- MSD (Most Significant Digit) Sorting: Lexicographic Order. Better for strings.
- Uses Counting Sort as Sub Routine (which takes extra memory)
- If memory is not really a concern, forget about this issue
- Radix Sort, with at most d digits, takes O(d*(n+b)) time where b is the base
- Use Radix Sort over Counting Sort when the numbers range from 1 to n-square for example.
Let’s look at the stats from the algorithm:
|# of Items in Array||Time Taken||Average for 100 numbers|
As always, the code is available at https://github.com/abhi1010/Algorithms for easier access.