Anonymous Monk says:

Well, you can't sort infinite streams.

Sometimes you can sort infinite streams. It depends on the stream and the sort order. Section 6.5.3 of Higher-Order Perl discusses it in some detail. The example on page 293-300 is to sort the contents of qmail's log file while the log is being written.

One kind of cool thing about the lazy streams is that if you implement quicksort in the straightforward way, you get a reasonably good lazy sorting function that does run in O(n log n) average time. And if you're only looking at a few elements from the front of the sorted result, the time is O(n).

Put another way, we sometimes laugh when beginners write this:

        my ($minimum) = sort @items;
[download]

because we know that the sort is O(n log n), and there's a straightforward algorithm for the minimum that is O(n). But if your sort algorithm is implemented lazily, as it probably is if the array is actually a lazy list, then the code above does run in O(n) time, because the sort call only sorts enough of the list to find the minimum element. Code like that above does run in linear time in Haskell, for example. Of course, as you say, the whole stream must be resident in memory.

I didn't put this into HOP because although I thought it was delightful and fascinating, it didn't seem to have any immediate practical use.