Front page | perl.perl5.porters |
Postings from September 2013
On Fri, Sep 06, 2013 at 02:59:44PM -0400, John P. Linderman wrote: > > Part of the reason, I think, was that v5.6 and earlier's sort was a > > quicksort, and hence not a stable sort. > > Stability was definitely a feature, but my best argument to Jarkko was that > far too many common sequences (organ pipe, sawtooth, etc.) went quadratic, > and Peter Mcilroy's merge sort did a particularly nice job on sequences > with pre-existing order (linear time on sorted input). > > The only sequences (that I could think of, anyway) where it was clear that > qsort would outperform merge sort were those containing many repetitions of > a small number (k) of keys. Qsort's "fat pivot" guaranteed that only k > passes would be required, where merge sort might need log N. The bit that keeps bugging me is "how many people know that their data is usually going to be in a particular form that qsort favours"? In that, the amount of use cases where it's correct to specify qsort instead of mergesort are small, the amount of effort needed to determine this is high, and the gain itself is small? In which case, seems that choosing a specific sort algorithm is not the first place to look at optimising. Nicholas ClarkThread Previous | Thread Next