# Introduction/Direct Translation

The quicksort quoted in Introduction isn't the "real" quicksort and doesn't scale for longer lists like the c code does.

Here are some points to how the "real" quicksort would look in haskell.

Lennart Augustsson has a quicksort entry on his blog which is pure (no unsafe):

Another version (uses System.IO.Unsafe), is below.

There is also a "parallel" quicksort at

roconnor claims that in haskell the "real" quicksort is really a treesort:

Unfortunately none of the above "real" quicksorts seems to compile as given, when copy/pasted into ghci. Can someone fix? The "parallel" quicksort gave error "unknown package concurrent" when I ran make in quicksort/gransim.

Has anyone got a functioning "real" quicksort that works on copy/paste?

The program below is working very very slowly. It's probably slowsort... :o)

import Data.Array.ST
import Data.Array.IArray
import Data.Array.MArray

qsort :: (IArray a e, Ix i, Enum i, Ord e) => a i e -> a i e
qsort arr = processArray quickSort arr

processArray :: (IArray a e, IArray b e, Ix i)
=> (forall s. (STArray s) i e -> ST s ()) -> a i e -> b i e
processArray f (arr :: a i e) = runST \$ do
arr' <- thaw arr :: ST s (STArray s i e)
f arr'
unsafeFreeze arr'

quickSort :: (MArray a e m, Ix i, Enum i, Ord e) => a i e -> m ()
quickSort arr = qsort' =<< getBounds arr
where
qsort' (lo, hi) | lo >= hi  = return ()
| otherwise = do
l <- mainLoop p lo hi
swap l hi
qsort' (lo, pred l)
qsort' (succ l, hi)

mainLoop p l h  | l >= h    = return l
| otherwise = do
l' <- doTil (\l' b -> l' < h  && b <= p) succ l
h' <- doTil (\h' b -> h' > l' && b >= p) pred h
when (l' < h') \$ do
swap l' h'
mainLoop p l' h'

doTil p op ix = do