A Sort Optimization Technique: decorate-sort-dedecorate

[Duncan Booth]

Tim Peters wrote:

> [/T]
>>> OTOH, current versions of Python (and Perl)
> 
> [/F]
>> just curious, but all this use of (& Perl) mean that the Perl folks have
>> implemented timsort ?
> 
> A remarkable case of independent harmonic convergence:
> 
>     http://mail.python.org/pipermail/python-dev/2002-July/026946.html
> 
> Come to think of it, I don't actually know whether a /released/ Perl
> ever contained the development code I saw.  Looks like it got added to
> Perl 5.8:
> 
>     http://perldoc.perl.org/sort.html
> 
The difference in style between Perl and Python is quite interesting: Perl 
lets you specify the algorithm which you think it going to be best for your 
code, but in a global manner which means your pragmas may or may not have 
the desired effect (which sounds a headache for maintenance). Python simply 
gets on with the job.

What the perl docs don't say though is whether they do any of the fancy 
timsort optimisations. I guess not, or at least not all of them: the Perl 
docs warn that mergesort can be much slower if there are a lot of 
duplicates, and from the Python dev thread above we can see that early 
timsort was also much slower for that case (~sort) but in the final version 
there is no effective difference.