G'day Ton/P5P, Ton Hospel wrote: > Mergesort works well too if you cut off runs at M. You're absolutely right. Quicksort throws away unnecessary elements at the start (except in pathological cases). Mergesort throws them away at the end (once runs start to become bigger than M). Both of them become much faster by having M < N. In the end, I would expect the complexity to be the same. > And since the plain sort already is mergesort, i think that would be > the best choice since it will e.g. have the same stability properties, > and the partial sort smoothly extends to the full sort. I'm inclined to agree here. If regular sort is simply a special case of truncated sort, then it avoids the unpalatable idea of having to maintain two separate sorts in Perl. This is a good thing. The question still remains as to what should happen when sort is called in a scalar context. Does it return the smallest value, the sortedness value, or play nethack? ;) Cheers, Paul -- Paul Fenwick <pjf@perltraining.com.au> | http://perltraining.com.au/ Director of Training | Ph: +61 3 9354 6001 Perl Training Australia | Fax: +61 3 9354 2681Thread Previous | Thread Next