While we're blue skying things, I've had an idea for a sorting algorithm
kicking around for a couple of years that might be interesting. It's a
variation on heapsort to make it significantly more block-friendly. I
have no idea if the idea would work, or how well it'd work, but it might
be worthwhile kicking around.
Now, the core idea of heapsort is that the array is put into heap order-
basically, that a[i] >= a[2i+1] and a[i] >= a[2i+2] (doing the 0-based
array version here). The problem is that, assuming that the length of a
is larger than memory, then a[2i+1] is likely going to be on a different
page or block than a[i]. That means every time you have to bubble down
a new element, you end up reading O(log N) blocks- this is *per element*.
The variation is to instead work with blocks, so you have a block of
entries b[i], and you change the definition of heap order, so that
min(b[i]) >= max(b[2i+1]) and min(b[i]) >= max(b[2i+2]). Also, during
bubble down, you need to be carefull to only change the minimum value of
one of the two child blocks b[2i+1] and b[2i+2]. Other than that, the
algorithm works as normal. The advantage of doing it this way is that
while each bubble down still takes O(log N) blocks being touched, you
get a entire block worth of results for your effort. Make your blocks
large enough (say, 1/4 the size of workmem) and you greatly reduce N,
the number of blocks you have to deal with, and get much better I/O
(when you're reading, you're reading megabytes at a shot).
Now, there are boatloads of complexities I'm glossing over here. This
is more of a sketch of the idea. But it's something to consider.
Brian
