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 22:30
Re: [perl #119635] deprecate and remove qsort?
Message ID:
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