Haskell Quicksort efficiency

Question

Here's an example from Learn you a Haskell:

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

It seems that the list is iterated twice for each recursion, once for each list comprehension. Is there some magic in the compiler that optimizes this? If not, how can this be fixed?

Edit: I don't care if this is a real quicksort. Ignore the quicksort. My question is about the efficiency of the two list comprehensions, and how you can modify this specific algorithm (quicksort or not) in order to avoid iterating xs twice per recursion.

I thought this would be more efficient: `let (l,g) = partition (<=x) xs in l ++ [x] ++ g`. — shouya, Apr 27 '14 at 03:46
I suggest you read http://stackoverflow.com/questions/7717691/why-is-the-minimalist-example-haskell-quicksort-not-a-true-quicksort — Thomas M. DuBuisson, Apr 27 '14 at 03:50
your question was asked (and answered) at http://stackoverflow.com/questions/7641936/is-it-possible-to-do-quicksort-of-a-list-with-only-one-passing/9550430#9550430. — Will Ness, Apr 27 '14 at 17:39

score -1 · Answer 1 · edited May 23 '17 at 12:20

No. As of now, GHC 7.8.2 is not smart enough to figure out the clever in place quicksort algorithm from the above quicksort definition. You can do the same thing in a single pass by defining quicksort as

import Data.List (partition)
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = let (psx1, psx2, psx3) = partition3 x (x:xs) in
                   quicksort psx1 ++ psx2 ++ quicksort psx3

partition3 _ [] = ([], [], [])
partition3 a (x:xs)
    | a == x = (pxs1, x:pxs2, pxs3)
    | a < x = (pxs1, pxs2, x:pxs3)
    | a > x = (x:pxs1, pxs2, pxs3)
    where (pxs1, pxs2, pxs3) = partition3 a xs

But you should check is it possible to do quicksort of a list with only one passing? as it is more efficient than the above version.

I appreciate the effort but this doesn't answer my question – ConditionRacer Apr 27 '14 at 17:18 — ConditionRacer, Apr 27 '14 at 17:18

Haskell Quicksort efficiency

1 Answers1

Linked