Well, you can't sort infinite streams.

Yeah, but streams need not be infinite. (At least according to HOP, which is what chb referred to. See HOP, pp. 257-259.) Streams only need to be lazy; in fact, the first example of a stream that Dominus gives (upto, p. 259) is a finite one. Since the stream in question would consist of the lines of a file at a given point in time, it goes without saying that such stream would necessarily be finite.