on Mon Apr 27 2009, Steven Ross <spreadsort-AT-gmail.com> 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 MAX_SPLITS and (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT), and would take 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 http://www.boostpro.com