[boost] sorting library proposal (Was: Review Wizard Status Report for June 2009)o

Subject: [boost] sorting library proposal (Was: Review Wizard Status Report for June 2009)o
From: Vladimir Prus (vladimir_at_[hidden])
Date: 2009-06-02 00:54:13

Ronald Garcia wrote:

> Sorting
> -------
> :Author: Steven Ross
> 
> :Review Manager: Needed
> 
> :Download: `Boost Vault
> :<http://www.boostpro.com/vault/index.php?action=downloadfile&amp;filename=algorithm_sorting.zip
>  >`__
> 
> :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