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

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

Thread Previous | Thread Next
Victor Efimov
September 7, 2013 08:18
Re: [perl #119635] deprecate and remove qsort?
Message ID:
I was able to reproduce case when qsort do 3 times less comparison than

However I was unable to find case when qsort faster when comparsion
function is simple, obvious this can be the case for complex comparison
functions. One also can/should use anyway if comparison
function is always slow, an this limits benefits of qsort.

use strict;
use warnings;

my @a = (1..3) x 100_000;
our $i;

sub mysub
$a <=> $b;

my ($q, $m);
 use sort '_quicksort';
 local $i=0;
 my @b = sort mysub @a;
 $q = $i;
 print "quicksort: $i\n";
 local $i=0;
 my @b = sort mysub @a;
 $m = $i;
 print "mergesort: $i\n";

print $q/$m, "\n";
quicksort: 599997
mergesort: 1746356

2013/9/7 John P. Linderman <>

> All true, all valid observations.  The merge sort implementation uses N
> additional *pointers* (not records), the qsort implementation sorts in
> place (unless you want stability, in which case it, too, uses another set
> of pointers, same as the merge sort implementation).  I started programming
> back in the 60's, when a few kilobytes of memory was all that there was,
> and you'd do all sorts of things that would now be considered inexcusable
> to save a few bytes (like using only the last two digits of the year,
> leading to the Y2K "crisis"). I often have to remind myself that memory is
> now darn near free, but my time is more expensive every year (at least
> until AT&T "surplussed" me).  If you need to worry about double the number
> of pointers, perhaps perl is not the implementation language you should be
> using.  Qsort, with its divide and conquer approach, automatically ends up
> doing a lot of processing in the fastest (i.e. smallest) cache, which is
> quite ironic, since quicksort was invented when memory was monolithic, and
> caches didn't exist.  But I attempted to fix that flaw in merge sort (at
> the expense of some additional stack space... it took some discipline to
> ignore that in the environment I now program in rather than one where I
> learned to program :-).  My attitude now (since you didn't ask :-) is that
> space matters a whole lot less than time, and cache hits matter, because
> they have a major impact on time.  And maintainability matters a lot too,
> because it relates to correctness, which really matters more than just
> about everything, which is why I wouldn't much mind qsort disappearing.  I
> hope to live long enough to experience another major paradigm shift (like
> exploiting multiple processors in parallel).
> On Fri, Sep 6, 2013 at 3:34 PM, Victor Efimov <> wrote:
>> 2013/9/6 John P. Linderman <>
>> 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.
>> Seems memory usage can be better with qsort than with mergesort (not sure
>> about perl implementation).
>> ===
>> Merge sort's most common implementation does not sort in place;
>> therefore, the memory size of the input must be allocated for the sorted
>> output to be stored in (see below for versions that need only *n*/2
>> extra spaces).
>> ===
>> ===
>> The disadvantage of the simple version above is that it requires O(*n*)
>> extra storage space, which is as bad as merge sort<>.
>> The additional memory allocations required can also drastically impact
>> speed and cache performance in practical implementations. There is a more
>> complex version which uses an in-place<>partition algorithm and can achieve the complete sort using O(log
>> *n*) space (not counting the input) on average (for the call stack<>).
>> We start with a partition function:
>> ===

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