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:
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
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.