Quicksort

Quicksort is one of the most used Algorithm in computer science. It is based on the idea of recursive partitioning. The partition scheme is always linear but the expected problem sizes at each iteration can be data dependent. Hence the expected O(nlogn) time comes. However, its a very useful algorithm because the time complexity is fairly tight and that's the reason it can achieve close of nlogn speed for most of the cases.
Implentation of partition in place is not trivial and history proved that with many buggy variants of partition in 60sHowever, A functional (haskel) version of Quicksort can be wrtten in a very precise and short manner:

qsort []     = []
qsort (x:xs) = qsort less ++ [x] ++ qsort more
  where less = filter ()  xs
        more = filter (>=x) xs