Compile: ghc --make -eventlog -threaded -rtsopts ParallelQuicksort.hs Execute: ./parqsort +RTS -s -l -N4 -H500M # (for example)

ParallelQuicksort.hs

module Main where

import Control.Parallel.Strategies
import Data.List

-- Standard quicksort
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = let smaller = [e | e <- xs, e <= x]
                   bigger = [e | e <- xs, e > x]
               in qsort smaller ++ [x] ++ qsort bigger

{- Read numbers from a string with newlines;
   create such a file using
       while true; do echo $RANDOM >> rannum.txt; done
-}
readNumbers :: String -> [Int]
readNumbers [] = []
readNumbers s = map read . lines $ s

-- Quicksort using Strategies Parallelization
stratqsort :: (Ord a) => [a] -> [a]
stratqsort [] = []
stratqsort (x:xs) = runEval $ do
    a <- rpar (stratqsort [e | e <- xs, e <= x]) -- Sublists are extracted and sorted in a spark'd evaluation
    b <- rpar (stratqsort [e | e <- xs, e > x])
    return (a ++ [x] ++ b)

-- Modest memory usage (39M maximum residency); works best with huge heap (+RTS -H500M)
-- This functions needs on my machine about 32 seconds.
main1 = do
    c <- readFile "rannum2.txt"
    writeFile "sorted.txt" (concat . intersperse "\n" . map show . stratqsort . readNumbers $ c)

-- This one needs one third, about 11 seconds. Why is that?
main2 = do
    c <- readFile "rannum2.txt"
    let n = readNumbers c
    let s = stratqsort n
    let o = concat . intersperse "\n" . map show $ s
    writeFile "sorted.txt" o

-- main3 is even faster than main2!
main3 = do
    c <- readFile "rannum2.txt"
    writeFile "sorted.txt" . concat . intersperse "\n" . map show . stratqsort . readNumbers $ c