Ah, it would keep O(k) in memory, yeah. Which could certainly be problematic.

I don't think there is a scalable 1-pass algorithm for large k. But I think a scalable 2 pass algorithm (which is easy) is still probably preferable in most cases to something that shuffles the entire data set?