What is wrong with this Haskell quicksort

Question

Taking the functional programming plunge and trying to teach myself Haskell from online materials. Probably pretty basic, but I cannot figure why my implementation of quicksort does not terminate for any input list with length longer than 1.

Here's the code:

quicksort :: (Ord ord) => [ord] -> [ord
quicksort [] = []
quicksort [element] = [element]
quicksort array = quicksort right_half ++ [pivot] ++ quicksort left_half
  where pivot = head array
        right_half = [element | element <- array, element <= pivot]
        left_half = [element | element <- array, element > pivot]

I was reading an online textbook but decided to try the quicksort for myself before just reading the given solution. After failing, I went back and understood the given answer, but still cannot see why mine is wrong. Any help for this haskell newbie would be appreciated!

Answer 1

Notice that this sort of algorithm is not going to yield quick sort. The time complexity of (++) will destroy you, if nothing else.

As for your problem, you are taking all elements that are <= pivot.. which will (absolutely) include the pivot. So if you have a list [2,1] then to sort that your right half will call quicksort [2,1], thus creating a loop.

A better solution is to pattern match, using something like:

quicksort (pivot:array) = quicksort rightHalf ++ [pivot] ++ quicksort leftHalf

Edit: see the related Why is the minimalist, example Haskell quicksort not a "true" quicksort?