News for hackers. Stuff that matters.
Re:Tree Oriented Programming [pdf] by jacobparker on Monday April 24, 2017 @07:53AM (#14183475)
It isn't. Perhaps you're missing the recursion (which, at each step, does two of those list appends.)

Write this algorithm in an imperative language and it'll pretty clear that this is best/expected case O(n^2).

Re:Tree Oriented Programming [pdf] by vilhelm_s on Monday April 24, 2017 @09:47AM (#14184239)
It doesn't matter that it's two list appends, 2*O(n) is still O(n).

Suppose the length of (qsort (filter (<x) xs)) is k. Then the time to do the two appends in (qsort (filter (<x) xs)) ++ [x] ++ (qsort (filter (>=x) xs)) is k + (k+1), which is linear in k.

At the same time any quicksort (even an in-place one) will scan through the entire array once in order to partition it, which also takes linear time. (It will take time proportional to the length of the entire array, not just the first half.) The extra work from the appends only changes the constant factors, not the asymptotics.