# Solved: quicksort

Quicksort is one of the most efficient sorting algorithms, boasting an average time complexity of O(n log n). Based on the divide-and-conquer methodology, it exhibits impressive performance when sorting large datasets. Invented by British computer scientist Tony Hoare in 1959 and published in 1961, quicksort has become a fundamental part of computer science and programming.

Quicksort’s popularity is also due to its ease of implementation in various programming languages. In this article, we’ll delve into how quicksort can be implemented using the Haskell programming language, a statically-typed functional programming language known for its purity, conciseness, and elegance.

## How does Quicksort work?

Quicksort operates by selecting a ‘pivot’ from the dataset and dividing the other elements into two groups – those less than the pivot and those greater than the pivot. This step, known as ‘partitioning’, is carried out recursively until the list is sorted.

```quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser  = filter (<  p) xs
greater = filter (>= p) xs
```

The above Haskell code begins by defining a base case for an empty list, which returns an empty list. For a non-empty list, it selects a pivot (in this case, the first element of the list), then filters the rest of the list into two sublists – one with elements less than the pivot, and one with elements greater than or equal to the pivot.

In our Haskell implementation, we make use of the language’s powerful list comprehension and higher-order functions.

The line of code `(quicksort lesser) ++ [p] ++ (quicksort greater)` concisely captures the essence of quicksort – it recursively sorts both the `lesser` and `greater` sublists, then concatenates these sorted sublists with the pivot in the middle. This is the divide and conquer strategy in action.

Despite its simplicity, this implementation can be inefficient for larger lists, as it filters each sublist twice. Nonetheless, it serves as a great starting point for understanding how quicksort works in Haskell.