Quicksort in Haskell

Here is my attempt at quicksort in Haskell

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =  smaller ++ [x] ++ bigger
                   where smaller = quicksort [y| y <- xs , y < x]
                         bigger = quicksort [y | y <- xs, y >= x]
      

So how does this work?

• [a] ->[a] means that quicksort takes a list as input and returns a list as output


• (Ord a) means that a belongs to a type class Ord (i.e. a is an ordered type)


• The first expression means that quicksort returns an empty list for an input empty list


• The second expression works as follows. The input list is broken into its head and tail (x, xs). We use x as the pivot element. all elements smaller than x in xs are identified and sorted using quicksort itself (recursively). All elements greater than or equal to x are sorted by quicksort itself (recursively). The final result is smaller + [x] + bigger.

So here are some examples:

*Main> quicksort [2, 1, 3]
[1,2,3]
*Main> quicksort "i don't believe you"
"   'bdeeeiilnootuvy"
*Main> quicksort "i love you"
"  eiloouvy"
*Main> quicksort [50, 40, 30 , 10, 20, 30, 40, 50, 20]
[10,20,20,30,30,40,40,50,50]
*Main>