I am learning Haskell programming language mainly from this source. And there I have encouraged with "an elegant" realization of the quicksort sorting algorithm (the Quick, sort! section). Here it is:

#Book's implementation 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

The problem with this implementation (as I think) is doubled number of comparisons inside the let binding every time. Isn't the fact that those of a's that already in the smallerSorted list cannot be in the biggerSorted list, so we don't need to compare x with them anymore.

In order to "improve" the above approach I have written my own implementation, where I use auxiliary local function split that splits a list into two parts: less than (or equal to) x and greater than x.

#My implementation

quick_sort :: (Ord a) => [a] -> [a]
quick_sort []       = [] --edge condition 
quick_sort (x : xs) =    --general condition
    let (lt, gt) = split x xs
    in  (quick_sort lt) ++ [x] ++ (quick_sort gt) 
    where
        --split function is used to split a list
        --into two sublists: one for elements
        --less or equal (lt) than some value - x
        --and one for those that greater (gt) than x
        --NOTE: split function is also recursive
        split x [] = ([], []) --edge condition
        split x (h : hs)      --general condition
            | h <= x    =
                let (lt, gt) = split x hs
                in ( (h : lt), gt )
            | otherwise =
                let (lt, gt) = split x hs
                in ( lt, (h : gt) )

P.S. For a while I am not able to compare two approaches, but on the worst cases (when list to sort is already sorted) it seems that my implementation is a bit slower.