🚀 go-pugleaf

frank@D012S436.sniap.mchp.sni.de () writes:

>I'm writing a program which needs to sort a large array 
>parts of which are swapped in and out of memory (my own
>implementation of a sort of VM).

>The array is divided up into pages of size ~8K which are
>swapped to disk as necessary on a LRU basis.  

>Does anyone know of a sorting algorithm which will work in 
>harmony with this LRU paging?  I can quicksort the elements 
>of each individual page of the array, but then the problem 
>is to sort the pages themselves with the minimum amount 
>of swapping.  Traditional sort alrgorithms optimise on
>comparisons - what I want is also to optimise the *order*
>of comparison, I think.  Any ideas?

Would it be feasible to consider each page somewhat like a "stack", and 
"pop" the lowest one off whichever stack holds it?  I.e. sort each page 
(stack) and then compare the "top card" from each stack.  If it is the
lowest (highest if a descending sort), write it to output and pop that
stack.  It doesn't matter which stack gets emptied first, or how quickly,
since you will always be "popping" the lowest (| highest) value off of
whichever stack has it.  Think of it like piles of playing cards, face up.
Each pile is already sorted.  You just take the lowest (| highest) card
showing and put it directly in your output pile.  When done, the output pile
will be sorted (though in reverse order).  In your algorithm, you only need
to read the page for the stack you just popped; the "top cards" from all
other stacks simply remain in memory for comparison.  You reread the popped
stack for the next value, and then rewrite it minus the value you popped.
Of course, if the same stack has the next lower value as well, you needn't
reread it, as it is the one still in memory.  You can make this faster if
you write each stack as a random-access file once it is sorted.  This way, you
only need to read single values from any given stack, and merely update its
file pointer.

Hope this helps. 

-JTT