quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerOrEqual = [a | a <- xs, a <= x]
larger = [a | a <- xs, a > x]
in quicksort smallerOrEqual ++ [x] ++ quicksort larger
The above diagram illustrates how quicksort works on our example. When we want to sort [5,1,9,4,6,7,3], we decide that the first element is our pivot. Then we sandwich it in between [1,4,3] and [9,6,7]. Once we’ve done that, we sort [1,4,3] and [9,6,7] by using the same approach.
To sort [1,4,3], we choose the first element, 1, as the pivot and we make a list of elements that are less than or equal to 1. That turns out to be the empty list, [], because 1 is the smallest element in [1,4,3]. The elements larger than 1 go to its right, so that’s [4,3]. Again, [4,3] is sorted in the same way. It too will eventually be broken up into empty lists and put back together.
The algorithm then returns to the right side of 1, which has the empty list on its left side. Suddenly, we have [1,3,4], which is sorted. This is kept on the left side of the 5.
Once the elements on the right side of the 5 are sorted in the same way, we will have a completely sorted list: [1,3,4,5,6,7,9].