Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

file 44 lines (37 sloc) 1.477 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
module Sorting where

import Control.Parallel (par, pseq)

sort :: (Ord a) => [a] -> [a]
sort (x:xs) = lesser ++ x:greater
    where lesser = sort [y | y <- xs, y < x]
          greater = sort [y | y <- xs, y >= x]
sort _ = []

parSort :: (Ord a) => [a] -> [a]
parSort (x:xs) = force greater `par` (force lesser `pseq`
                                         (lesser ++ x:greater))
    where lesser = parSort [y | y <- xs, y < x]
          greater = parSort [y | y <- xs, y >= x]
parSort _ = []

seqSort :: (Ord a) => [a] -> [a]
seqSort (x:xs) = lesser `pseq` (greater `pseq`
                                (lesser ++ x:greater))
    where lesser = seqSort [y | y <- xs, y < x]
          greater = seqSort [y | y <- xs, y >= x]
seqSort _ = []

force :: [a] -> ()
force xs = go xs `pseq` ()
    where go (_:xs) = go xs
          go [] = 1

sillySort (x:xs) = greater `par` (lesser `pseq`
                                  (lesser ++ x:greater))
    where lesser = sillySort [y | y <- xs, y < x]
          greater = sillySort [y | y <- xs, y >= x]
sillySort _ = []

parSort2 :: (Ord a) => Int -> [a] -> [a]
parSort2 d list@(x:xs)
  | d <= 0 = sort list
  | otherwise = force greater `par` (force lesser `pseq`
                                     (lesser ++ x:greater))
      where lesser = parSort2 d' [y | y <- xs, y < x]
            greater = parSort2 d' [y | y <- xs, y >= x]
            d' = d - 1
parSort2 _ _ = []
Something went wrong with that request. Please try again.