Haskell has a particularly elegant implementation of the quicksort algorithm:
qs :: (Ord a) => [a] -> [a] qs  =  qs (x:xs) = let smaller = qs [a | a <- xs, a <= x] bigger = qs [a | a <- xs, a > x] in smaller ++ [x] ++ bigger
This algorithm creates a new array that is sorted instead of sorting the given array in place. Therefore, there is no point in implementing a partitioning strategy (usually Hoare’s).
qs :: (Ord a) => [a] -> [a]
This is just a type signature which can be read like this: “
qs is a function that takes and array of
as and produces a new array of
as where each element
a can be compared to another.” The
(Ord a) part is a type constraint that means that
as need to be comparable, which makes sense since this is a sorting algorithm.
qs  =  qs (x:xs) = -- and so on...
let smaller = qs [a | a <- xs, a <= x] bigger = qs [a | a <- xs, a > x] in smaller ++ [x] ++ bigger
In Haskell, everything is an expression instead of a statement. Expressions are things that produce values. Statements are just lines of code that do something. Sometimes, it is useful to define intermediate values in an expression, and that is what the let block does. The result of the block is an array of
smaller ++ [x] ++ bigger.
[a | a <- xs, a <= x]
List comprehension generates lists (or arrays) using generators and guards (or filters). This code can be read “give me a list of
as where each
a is taken from the
xs list and is less than or equal to
x.” (This is really just syntactic sugar on top of do notation, which itself is just syntactic sugar for monadic composition, but that’s a topic for another time.)
xs.filter(s => s <= x). Arrow functions enable a relatively elegant alternative.
Here’s the cool trick to put everything together: since there are only two branches of logic, the ternary operator provides a great mechanism for handling the conditions. We can use destructuring to split the array to its head and tail. Then we use the ternary operator to return an empty array if the head is undefined (since the array was empty), or the new array made up of the smaller array, current element, and bigger array. Here is the final code:
// qs :: (Ord a) => [a] -> [a] (from Haskell) const qs = ([x, ...xs]) => x ? [ ...qs(xs.filter(s => s <= x)), x, ...qs(xs.filter(b => b > x)) ] : 
The coolest part of this implementation is that the whole thing is just an expression! There are no variable declarations at all (except the quicksort algorithm itself being assigned to a constant).