Encoding-wise, Elias-Fano requires exactly 2 + ceil(log(2^32 / n)) bits, so it would provably fit in the memory budget. Algorithm-wise, yeah I can only think o

Encoding-wise, Elias-Fano requires exactly 2 + ceil(log(2^32 / n)) bits, so it would provably fit in the memory budget. Algorithm-wise, yeah I can only think of quadratic ones. But if in the question the bottleneck is memory, maybe that's fine? An optimization would be to do selection sort, but in each round select the next group of integers that share the top 32 - ceil(log(2^32 / n)) bits, as that is a cluster in the EF representation, and then sort the lower bits, which can be done in-place in O(k log k) where k is the group size. So if your groups are large enough you get some speedup. EDIT: Ah I think that the trick is to always use half of the memory left to read and sort. - Read 256k integers (1MB), sort in-place, construct EF representation (~500kB) - Read 128k, sort, and produce another EF (~280kB) - Keep halving You do a logarithmic number of rounds, so it's O(n log n). At the end you're left with log(n) EF sets, which fit in less than 2MB (in fact there's some space left, and you could save a few rounds) and you can merge them with a log(n)-way heap into a stream.