It would be pretty difficult to write an in-place sort in Haskell, given that it only has mutable state through monads (and I doubt anyone wants to go into a mo

It would be pretty difficult to write an in-place sort in Haskell, given that it only has mutable state through monads (and I doubt anyone wants to go into a monad just to sort something). GHC is pretty good at optimizing list concatenations, so that's probably not a big deal either. You're absolutely right about the two-pass filter, though.