[throwaway_yy2Di]

This works, and is so much simpler.

It's not quite the same problem though; the algorithm described returns samples in sequential order. They mention performance reasons for this (C-f "tape sampling"). It also has the limitation that you need to know the sample size in advance.

[vrfcodf]

MLCG is sequential. No value will be repeated within the period.

[tomp]

"sequential" in the sense that if returned values are i1, i2, ..., in, then 0 <= i1 < i2 < ... < in <= N.

A MLCG will return numbers all over the place; sorting them will take an additional O(n log n) time.

[vrfcodf]

I see.

[tomsmeding]

He means: outputs are sorted.