Ronald Garcia wrote:
Sorting ------- :Author: Steven Ross
:Review Manager: Needed
:Download: `Boost Vault :<http://www.boostpro.com/vault/index.php?action=downloadfile&filename=alg...
`__
:Description: A grouping of 3 templated hybrid radix/comparison-based sorting algorithms that provide superior worst-case and average-case performance to std::sort: integer_sort, which sorts fixed-size data types that support a rightshift (default of >>) and a comparison (default of <) operator. float_sort, which sorts standard floating-point numbers by safely casting them to integers. string_sort, which sorts variable-length data types, and is optimized for 8-bit character strings.
All 3 algorithms have O(n(k/s + s)) runtime where k is the number of bits in the data type and s is a constant, and limited memory overhead (in the kB for realistic inputs). In testing, integer_sort varies from 35% faster to 8X as fast as std::sort, depending on processor, compiler optimizations, and data distribution. float_sort is roughly 7X as fast as std::sort on x86 processors. string_sort is roughly 2X as fast as std::sort.
The archive pointed at above does not seem to have any documentation at all. I though that having docs is a requirement for having a review at all? It is also unclear how the performance measurements were made and the graphs obtained -- what test program should be run, with what compiler and compiler options and on what system. At the very minimum, this should be clearly documented so that everybody can obtain the same graphs, if necessary. However, I have a bigger concern. How do we know these algorithms are indeed correct, and how they stand in relation to other sorting algorithms? Steven has provided a link to his article: http://portal.acm.org/citation.cfm?id=691537 However, it does not seem that full text is available for this article, so it's not possible to know what other algorithms spreadsort was compared to. I could not find references to this article from newer ones either, so no comparison results from there. Is Boost supposed to be the place for reviewing new algorithms, as opposed to reviewing new implementations of otherwise established algorithms? - Volodya