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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk