Определение

quicksort :: (Ord a) => [a] –> [a]

quicksort [] = []

quicksort (x:xs) =

  let smallerSorted = quicksort [a | a <– xs, a <= x]

      biggerSorted = quicksort [a | a <– xs, a > x]

  in smallerSorted ++ [x] ++ biggerSorted

Давайте немного «погоняем» функцию – так сказать, испытаем её в действии:

ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]

[1,2,2,3,3,4,4,5,6,7,8,9,10]

ghci> quicksort "съешь ещё этих мягких французских булок, да выпей чаю"

"        ,ааабвгдеееёзииийккклмнопрсстууфхххцчшщъыьэюя"

Ура! Это именно то, чего я хотел!