pMergeSort

import Control.Parallel.Strategies

merge :: (Ord a) => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
    | x <= y =  x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys

pairList :: [[a]] -> [([a], [a])]
pairList (x1:x2:xs) = (x1, x2) : pairList xs
pairList (x:xs) = [(x, [])]
pairList [] = []

sort :: (Ord a) => [a] -> [a]
sort xs = k . map (:[]) $ xs where
    f = parMap rpar (uncurry merge)
    k [x] = x
    k xs = k . f . pairList $ xs