🚀 go-pugleaf

In article <7290002@hpfcso.FC.HP.COM> ericw@hpfcso.FC.HP.COM (Eric Widhalm) writes:
>/ hpfcso:comp.sources.d / frank@D012S436.sniap.mchp.sni.de () /  3:35 am  Aug 27, 1992 /
>I'm writing a program which needs to sort a large array 
>parts of which are swapped in and out of memory (my own
>...
>of swapping.  Traditional sort alrgorithms optimise on
>comparisons - what I want is also to optimise the *order*
>of comparison, I think.  Any ideas?

Quicksort isn't as bad as you think.  In one pass of Quicksort, the algorithm
scans the array *sequentially* from both ends, occasionally swapping elements.
Thus, in one pass of Quicksort, each page of the array is swapped in once.
Furthermore, once the component elements get smaller than 8K, quicksort needs
no swaps at all.  Thus, the swapping complexity of quicksort should be the
same as its comparison complexity, n**2 in the worst case, but n*log(n)
on the average.

If you really want to sort first and them merge, try one of the merge 
algorithms that we used to use for tape-based sorting (see Knuth for details).
Since rewinding a tape was *slow*, these algorithms tried to minimize the 
passes through the tapes, which might translate into minimizing the accesses
to the pages.
-- 
Joseph A. Reuter, Wizard-in-Training
Speaking for myself from reuter@venice.sedd.trw.com
"Olorin I was in the West that is forgotten." -- J.R.R. Tolkien
"You can't win, you can't break even, and you can't quit the game."