[CipherThrowaway]

You could flip the order and do a sequential read from the source with a random write to the destination. It sounds like this would still suffer from poor performance on the data mentioned in the article, but it is hard to feel like some kind of opportunity hasn't been missed with index permutation.

For example, using the permuted the index mod M rather than random draw in the first pass could avoid the whole issue of oversized piles and the extra wasted space per pile.