Is the following Haskell implementation of quicksort efficient?

user_1367948 0
Viewed 123

I found the following implementation of quicksort in the book titled Learn You Haskell.

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
    in  smallerSorted ++ [x] ++ biggerSorted

My question is, doesn't this undermine the efficiency of quicksort given that

  1. The ++ operation is rather expensive
  2. List comprehension is used to construct the two sublists?
quicksort algorithm functional-programming haskell
1 Answers

For an algorithmic point, it is not an in-place algorithm. Hence, it will not be as efficient as the traditional imperative implementations that you know. (Being in-place is a crucial aspect of the superb performance of quicksort-like sorting algorithms.)

It will run with quicksort's typical complexity (on average O(N * log(N)) with worst case O(N²)). Thus, it is efficient in the sense that it will be able to scale with inputs. But it will not be as fast as highly tuned implementations (e.g. see this question).

As a minor tweak, I remember replacing [x] ++ biggerSorted by (x:biggerSorted) was a low-hanging fruit to improve the performance slightly. That was many years ago, so perhaps optimizing compilers today can do that low-level optimization automatically.

user_7835100
Related