[boost] [sorting] Advantages of radixsort

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-03-18 18:25:27

Many people are questioning the speed of radixsort and radix quicksort. In
some cases, those people are right, and radixsorts should not be used.
However, speed of the function is not the only thing that makes it
attractive. If you have downloaded the radixsort.cpp file from vault, you
will find a class with an integer array with 5 integers, a complex operator<
function that can be used for std::sort, and an operator[] that can be used
for radixsort. The size of the complex operator is pretty large and grows
for each integer added to the array. However, the size of operator[] is
constant. For an example of how the complex operator< can affect a program,
consider the class used in the example program to be a template class, with
one template parameter for type and another for size. Not only does it
contain the complex operator<, but it has the same functionality as
std::vector. Because the size of the class is a template paramters,
every different combination of type and size results in a version of that
class is created. If that class were to be used in a full sized program, the
code bloat would be tremendous. Now, consider another template class, with
one paramter for type and another for size. For each size, it creates three
of the classes found in the program, each with a different size. Consider
that class to be used just as much as std::vector. Think about how much
excess code is created just from operator<, not to mention all of the other
functions that would realistically be found in a class that had the same
functionality as std::vector. However, if the single line operator[] is
used, there would still be extra code generated for it, but nowhere near as
much as a complex operator<. Even though the std::sort and operator< might
be faster that radixsort and operator[], the size of the executable will be
noticably smaller if radixsort and operator[] are used.