Este algoritmo segue uma estratégia chamada de “divisão e conquista”.

1. Quando a lista não é vazia, seleciona-se a cabeça da lista e parte-se a cauda em duas listas:
   • uma lista com os elementos que são mais pequenos do que a cabeça,
   • e outra lista com os restantes elementos (isto é, os que são maiores ou iguais à cabeça)
2. Depois ordenam-se estas listas mais pequenas pelo mesmo método.
3. Finalmente concatenam-se as listas ordenadas e a cabeça, de forma a que a lista final fique ordenada.

qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = (qsort l1) ++ [x] ++ (qsort l2)
		where (l1,l2) = parte x xs

A função parte pode ser feita usando a técnica de tupling

parte :: (Ord a) => a -> [a] -> ([a],[a])
parte x [] = ([],[])
parte x (y:ys) | y < x = (y:l1, l2)
               | otherwise = (l1, y:l2)
		where (l1,l2) = parte x ys

Atalhos :

• Função Quick Sort feita com listas por compreensão