Re: Possible F77 Code Improvement ??

On 2009-03-09, glen herrmannsfeldt <gah@xxxxxxxxxxxxxxxx> wrote:
nmm1@xxxxxxxxx wrote:

That is correct. One difference is that quicksort is far more amenable
to such tweaks. There is also the point that few people seem to apply
the same approach to list-merge, but there is far more difference
between a well-coded one and the normal codes than most people realise.

Not only in the algorithm but in the implementation. It is
easy to describe using recursion but, like most recursive algorithms,
usually faster done using a loop (and an array to stack subarray
positions). The last ones I was reading about don't recurse all
the way down, but instead leave small subarrays unsorted and then
run selection sort at the end. (Conveniently masking any mistakes
in the quicksort implementation.)

A common variant, in usage if not in the number of people who have
actually implemented it themselves [*], is introsort. That's basically
quicksorting and if it reaches a certain recursion depth (which
doesn't mean that the implementation itself must use recursion, of
course) it switches to heapsort. This avoids the O(N**2) worst-case
behaviour of quicksort while still having the performance benefits of
quicksort for the common cases. And yes, when each subarray is small
enough is switches to insertion sort.

[*] Introsort is usually the choice for std::sort() in the C++
standard library.


Relevant Pages

  • Re: Quicksort
    ... worth the bother of ensuring that the stack space was adequate. ... is to set a reasonable maximum on the recursion ... case, I usually use either selection sort or a bubble sort variant, such as ... suited to the problem areas of quicksort). ...
  • Re: Factorial
    ... >> strings faster than quicksort does. ... I've attached a fast Quicksort for strings (without recursion) at the end of ... Private Sub QSortAs String) ...
  • Re: The Lisp Curse
    ... IIRC, the only time I've ever did quicksort was in a programming class, ... The C spec.'s probably don't specify that qsort _has_ to be implemented as ... sort smaller lists. ... but that's not the fault of recursion; ...
  • Re: Why is recursion hard?
    ... I'd seen a quicksort in a programming class a few years ... > totally iterative and written in pretty old fortran. ... that the concept of recursion was not difficult. ...
  • Re: Quicksort
    ... quicksort, in some edge cases, gets bad performance; ... No overflow occurs if you simply perform ... recursion for the short subdivision. ...