If you're allowed to make multiple passes over your set, you might as apply an in-place comparison sort and get it down to O(n*log n) time with constant space. Their method has the advantage that the stream doesn't need to be stored -- events can be processed as they come in and then discarded, never storing the entire set.