develooper Front page | perl.perl5.porters | Postings from September 2013

Re: [perl #119635] deprecate and remove qsort?

Thread Previous | Thread Next
John P. Linderman
September 6, 2013 18:59
Re: [perl #119635] deprecate and remove qsort?
Message ID:
> 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.

My email address in pp_sort.c is shown as  That will
stop working in a year or so.  Better would be  Peter is
no longer at Lucent, so his email address,, probably
stopped working about a decade ago.  I don't have a current email address
for him.

I have no strong opinion about removing qsort.  Seems like a good idea to

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About