On Thu, 2004-07-08 at 21:14, david nicol wrote: > After finding runs, we can find the M best with M*R more comparisons. > Which may or may not be an improvement over a NlogM single pass. How > big do the numbers have to be before it's worth the expected 1.5*N > comparisons to find out how small R is, given that after determining R > we can still fall back to the single pass when M*R is larger than NlogM? while collecting runs we can give up on the whole deal when we have too many runs. Too many runs is : M*R > NlogM R > (NlogM)/M so, calculate that, then collect runs, if we make it through the whole array with fewer, shift elements off of runs, otherwise do a single pass with binary insertions. I'm sure everyone is sick of me posting less-than-fully-baked postings by now, I thank you for your continuing indulgence. -- david nicol "cat and buttered toast"