Sort, Part 2
(Up to Basic
Computer Science : Lists and Arrays
: Sorting Algorithms)
[Part 1] [Part
Still, there are some tradeoffs for Radix Sort that can make it
less preferable than other sorts.
The speed of Radix Sort largely depends on the inner basic operations,
and if the operations are not efficient enough, Radix
Sort can be slower than some other algorithms such as
Quick Sort and Merge Sort. These operations include the insert and
delete functions of the sublists and the process of isolating the
digit you want.
In the example above, the numbers were all of equal length, but
many times, this is not the case. If the numbers are not of the
same length, then a test is needed to check for additional digits
that need sorting. This can be one of the slowest parts of Radix
Sort, and it is one of the hardest to make efficient.
Radix Sort can also take up more space than other sorting
algorithms, since in addition to the array that will be sorted,
you need to have a sublist for each of the possible digits
or letters. If you are sorting pure English words, you will need
at least 26 different sublists, and if you are sorting alphanumeric
words or sentences, you will probably need more than 40 sublists
Since Radix Sort depends on the digits or letters, Radix Sort is
also much less flexible than other sorts. For every
different type of data, Radix Sort needs to be rewritten, and if
the sorting order changes, the sort needs to be rewritten again.
In short, Radix Sort takes more time to write, and it is very difficult
to write a general purpose Radix Sort that can handle all kinds
For many programs that need a fast sort, Radix Sort is a good choice.
Still, there are faster sorts, which is one reason why Radix
Sort is not used as much as some other sorts.
If you would like to study a commented version of the actual source
code, you can download one from our site:
Download from Source
Code Repository: sorts/radix.h