Boost logo

Boost :

Subject: Re: [boost] Review Request: Algorithm.Sorting
From: David Abrahams (dave_at_[hidden])
Date: 2009-04-28 13:27:40

on Mon Apr 27 2009, Steven Ross <> wrote:

> True worst-case has to be determined by determining the worst possible
> input, then feeding it to the algorithm.
> I believe I know what the real worst-case input is to this algorithm, and it
> will take O(n(bit_range/C - 1 + C)) time, where C is the smaller of
> some effort to construct, like the Quicksort worst-case. For 32-bit
> integers and the default constants I provide, C is 8, so it ends up being:
> n((32/8 -1) = 3 slow iterations + 8 std::sort iterations)). Based upon the
> value of LOG_CONST and the distribution it can also give up and use
> std::sort, but only after n is cut into small pieces, so that the log(n)
> factor is small.
> What I am referring to is that I ran tests with randomness ranging from 0 to
> 32 bits, and I compared the worst, average, and best runtimes among those.
> Graphs are included in the libs/algorithm/sorting directory, linked to from
> the index.html.

Thanks for clarifying, that helps.

Dave Abrahams
BoostPro Computing

Boost list run by bdawes at, gregod at, cpdaniel at, john at