I know the fastest sorting algorithm is quicksort. It is even named accordingly. I also know that its time complexity is on average O(nlog(n)). Is there ever a sorting algorithm in linear time?
Yes, it turns out. It is called radix sort, and it actually predates modern computer.
What is radix sort? Radix sort is to sort numbers digit by digit. Or sort words letter by letter. It is so named because it uses a buffer of which the size becomes the radix of the sorted numbers. The radix is the number of possible digits in one position. Using a buffer of size 10, you can sort 0 to 9 in one iteration; using a buffer of 256 you can sort 0 to 255 in one iteration. The size is chosen according to memory limits, and in exchange sorting each additional digit takes another iteration.
Radix sort was THE algorithm used by IBM card sorters, which inherited the algorithm from tabulating machines.
How is radix sort linear? The number of iterations you go through the list to be sorted does not depend on the number of items, but the maximum number of digits or letters of the items, which is often a lot fewer than the number of items. If you know the maximum in advance, like if you know you are sorting 32-bit integers with a radix 2, then your time complexity is at most O(32n), which is indeed linear.
Linear time is categorized as being faster than n-logarithmic time. But in real world usages, the logarithmic term in n-logarithmic time is often smaller than the constant term in linear time. For the logarithmic term to reach 32, the number of items you are sorting needs to reach 2^32, which is 4 billion.
With a larger radix, like 256, the constant term of radix sorting for 32-bit integers becomes 4 (=32/log(256)), and to reach that with a logarithmic term the number of items necessary becomes 16. But even above 16 items, when is the improvement in sorting speed worth the additional 1 MB of memory (256 32-bit integers)?
- All logarithmic above are base 2.
Top comments (0)