Also, for in-memory data comparison-based sorting is much slower than shuffling. Both asymptotically (O(n log n) vs O(n)) and in practice. I did not investigate if sorting algorithms not based on comparisons (e.g. radix sort) have competitive performance.
https://www.computerworld.com/article/2762287/microsoft-s-eu...
Probably performance wouldn't be as good as the OP article though.
Uniform sampling is also quite easy (and principled) - you can just take the first n records.
One reason cited in TFA for the half-shuffled files approach is that it's easy to rotate old data out of and new data into the half-shuffled files.
The downside is that it still needs one random read access per element, so cache friendly hierarchical algorithms, like the one described in the post, are probably still faster for on disk data.
