Re: [boost] Review Request: Algorithm.Sorting

Subject: Re: [boost] Review Request: Algorithm.Sorting
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-05-05 12:08:10

I thought of another optimization for mostly-sorted data.  Currently I
preprocess data so that mostly-sorted data won't be swapped as much, in a
fashion that doesn't substantially impact unsorted data performance (<1%
penalty).  During that preprocessing, I could make good estimate of how
well-sorted the data is, and if it is highly sorted (say >80% sorted), then
I could quit out and use std::sort.  That way the penalty on mostly-sorted
data for using integer_sort on Windows would be much smaller.
The bad part of that is it would eliminate the speed improvement seen on
MacOSX for mostly-sorted data, which is substantial, instead having a small
net penalty.  I decided not to make this change for that reason, but I
wanted to mention it as a possibility.
Comments?