And you'll notice, it still has to process the whole list on the first pass, so lazy lists don't really come into play.

Yes, lazy lists are what make the whole scheme elegant. The sort returns a lazy list of values, which is nothing more than a thunk, a promise to do some work in the future (i.e. there is no computation done, and there are no elements sitting around in memory). When you end up needing the value in @sorted[0] that thunk is evaluated (you get the minimal value in O(n) time). And when you need @sorted[1] you get that in another O(log(n)) time. Etc. You might want to check out the lazy language Haskell for all kinds of funky stuff that can be done lazily (and all perl monks know the value of Laziness!)