[boost] [sorting] Radix quicksort examples - sort within sort

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-03-17 19:27:12

Earlier, I loaded an example of how normal radix sort is useful. However,
radixsort is almost impossible to use on data with varying lengths, making
it unsiuted for strings. Luckily, the same "sort within sort" effect can
still be achieved through radix quicksort. Although radix_quicksort is a
string sort, it can be used for data of any type by using the
create_id_string function, which is like sprintf, but instead of printing
literal values for numbers (33 becomes "33"), the bytes are printed onto the
string(33 becomes '!' (33 is the ascii value for '!')). Therefore, you get a
fast sort that can accomplish what is called "sort within sort" k times
faster than normal quicksort, where k is the number of bytes in the string.
(normal quicksort is k(2 N log N), while radix quicksort is k + 2 N log N).
Unfortunantly, it is not obvious how to implement radix quicksort, so I
loaded an example of how to create an id string and use radix quicksort.