No. I think I missed you point. My comment about code complexity still applies somewhat. Storing the state of the sort and testing the corner cases can be difficult.
On Fri, Sep 17, 2010 at 12:19 PM, Luc Maisonobe <luc.maison...@free.fr>wrote: > > Moreover, since sort is n log n without a radix sort, then the > > increment selection algorithm can only win if 100 < log n which is pretty > > unlikely.* > > I don't understand. Partition-based selection algorithms are basically > partition-based sort algorithm where we recurse in only one of the > partition once the pivot has been chosen. Subsequent calls therefore > don't restart from an array of size n but from smaller sub-arrays, has > the pivot can be saved (at least the top level ones). If at the end the > number of selections is so high the array ends up to be completely > sorted, the total cost is probably not much higher than what an initial > sort would have done. It will be higher since their are some bookkeeping > to do, but not so much higher I think. Doing one call corresponds to > resuming the partial sort from the state resulting from previous calls. > > Did I miss something ?
