> What happens if for a sort that doesn't fit in memory,
> we build an array of the data to be returned on disk
> and do a tag sort of the keys plus the index into the array?

This is more or less what i can propose too

> Or have I missed the whole question?

No you right as always

Regards,
Vlad