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

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

Thread Previous | Thread Next
Victor Efimov
September 6, 2013 19:34
Re: [perl #119635] deprecate and remove qsort?
Message ID:
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
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
algorithm and can achieve the complete sort using O(log
*n*) space (not counting the input) on average (for the call
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