title: How can I optimize parallel sorting to improve temporal performance?
body: <p>I have an algorithm for parallel sorting a list of a given length:</p>
  
  <pre><code>import Control.Parallel (par, pseq)
  import Data.Time.Clock (diffUTCTime, getCurrentTime)
  import System.Environment (getArgs)
  import System.Random (StdGen, getStdGen, randoms)
  
  
  parSort :: (Ord a) =&gt; [a] -&gt; [a]
  parSort (x:xs)    = force greater `par` (force lesser `pseq`
                                           (lesser ++ x:greater))
      where lesser  = parSort [y | y &lt;- xs, y &lt;  x]
            greater = parSort [y | y &lt;- xs, y &gt;= x]
  parSort _         = []
  
  sort :: (Ord a) =&gt; [a] -&gt; [a]
  sort (x:xs) = lesser ++ x:greater
      where lesser  = sort [y | y &lt;- xs, y &lt;  x]
            greater = sort [y | y &lt;- xs, y &gt;= x]
  sort _ = []
  
  parSort2 :: (Ord a) =&gt; Int -&gt; [a] -&gt; [a]
  parSort2 d list@(x:xs)
    | d &lt;= 0     = sort list
    | otherwise = force greater `par` (force lesser `pseq`
                                       (lesser ++ x:greater))
        where lesser      = parSort2 d' [y | y &lt;- xs, y &lt;  x]
              greater     = parSort2 d' [y | y &lt;- xs, y &gt;= x]
              d' = d - 1
  parSort2 _ _              = []
  
  force :: [a] -&gt; ()
  force xs = go xs `pseq` ()
      where go (_:xs) = go xs
            go [] = 1
  
  
  randomInts :: Int -&gt; StdGen -&gt; [Int]
  randomInts k g = let result = take k (randoms g)
                   in force result `seq` result
  
  testFunction = parSort
  
  main = do
    args &lt;- getArgs
    let count | null args = 500000
              | otherwise = read (head args)
    input &lt;- randomInts count `fmap` getStdGen
    start &lt;- getCurrentTime
    let sorted = testFunction input
    putStrLn $ "Sort list N = " ++ show (length sorted)
    end &lt;- getCurrentTime
    putStrLn $ show (end `diffUTCTime` start) 
  </code></pre>
  
  <p>I want to get the time to perform parallel sorting on 2, 3 and 4 processor cores less than 1 core.
  At the moment, this result I can not achieve.
  Here are my program launches:</p>
  
  <pre><code>1. SortList +RTS -N1 -RTS 10000000
  time = 41.2 s
  2.SortList +RTS -N3 -RTS 10000000
  time = 39.55 s
  3.SortList +RTS -N4 -RTS 10000000
  time = 54.2 s
  </code></pre>
  
  <p>What can I do?</p>
  
  <p><strong>Update 1:</strong></p>
  
  <pre><code>testFunction = parSort2 60
  </code></pre>