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

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.