>Each list comprehension is O(n). O(n)+O(n)=O(n). Each iteration will roughly bisect the list, resulting in roughly log(n) iterations. Thus the one-liner is O(n*log(n)).
"I'm not disputing the scaling properties of that sort" = this proof does not convince me of anything I didn't already agree with. Was I unclear about what I was objecting to?
>
Haskell says nothing about how lists are implemented, so with respect to "true"ness (I'm not really sure what this means), we can cannot generalize. A sufficiently optimized Haskell compiler implemented in silicon would have the liberty of using the memory in-place.
"Trueness" means "doing the real QuickSort". The one you posted doesn't. You can get the real QuickSort, but not with one line. A better compiler might identify useful invariants; you were not using such a compiler.
But if you had such a compiler, you wouldn't need to write I that way; you could just specify what conditions the final sort would obey, and that would be enough. You wouldn't need to tell it to filter explicitly.
