Re: Possible F77 Code Improvement ??



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

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.

--
JB
.