2 ms·
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
by jacobparker 9y ago
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).
- vilhelm_s 9y agoIt 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.