Introduction:
In previous tutorials we've discussed the different sorting algorithms from Bubble Sort to Counting Sort. With the exception of Counting Sort all of these algorithms have one thing in common, they're restricted by the fact that they need to compare elements to sort. In the book 'Intro to Algorithms', they discuss a lower bound limit that all comparison sorting algorithms are restricted by. All current and future comparison algorithms can not beat that limit. You can find more information on that
here. As discussed in the counting sort tutorial we can beat this limit by eleminating the need for comparisons. The problem we faced in that tutorial, and what most books and papers will tell you, is that non-comparison sorting algorithms are only for integer data types. In this tutorial I am going to show you that this is not always the case by introducing you to the Radix Sort.
Prerequisites:
I will be discussing how to use the Cache to speed up the algorithm, please read the
Cache Efficiency section prior to this implementation.
The
Counting Sort Tutorial is also a requirement as I will be using this sort inside of the Radix Sort.