Re: [boost] Proposed templated integer_sort

From: Steven Ross (spreadsort_at_[hidden])
Date: 2008-07-29 23:00:44

Here's float_sort, which requires a RightShift functor.
For this functor RightShift(x, 0) >> n must equal RightShift(x, n), which is
stricter than integer_sort is.
float_sort sorts floats as integers, but flips the negative bins around to
get the exact same sorting order as std::sort.  Positives floats sort fine
via integer_sort.
A functor is required because of the cast operation; I don't see any generic
way to code a general cast operation.  The RightShift functor looks like
this:
struct rightshift {
    int operator()(const DATATYPE &x, const unsigned offset) const { return
*((int *)&x) >> offset; }
};
Note the cast.

NaNs get dumped in the last bucket by default, without special-casing.
std::sort dumps them randomly in the file because they evaluate as
equivalent to everything, which is a little odd, and behavior I have no
intention to emulate.

In my testing, float_sort takes 61% of the time that std::sort takes on 40MB
files, so the speedup is substantial.  float_sort takes about 10% longer
than integer_sort, while std::sort takes about 20% longer on floats than
ints.

I'll pretty this up a bit and add a version that takes a comparison functor,
then move on to string::sort, which will take more work.  That should
complete the sorting library I intend to propose adding to Boost.

Steve