title: (When) are parallel sorts practical and how do you write an efficient one?
body: <p>I'm working on a parallelization library for the D programming language.  Now that I'm pretty happy with the basic primitives (parallel foreach, map, reduce and tasks/futures), I'm starting to think about some higher level parallel algorithms.  Among the more obvious candidates for parallelization is sorting.</p>
  
  <p>My first question is, are parallelized versions of sorting algorithms useful in the real world, or are they mostly academic?  If they are useful, where are they useful?  I personally would seldom use them in my work, simply because I usually peg all of my cores at 100% using a much coarser grained level of parallelism than a single sort() call.</p>
  
  <p>Secondly, it seems like quick sort is almost embarrassingly parallel for large arrays, yet I can't get the near-linear speedups I believe I should be getting.  For a quick sort, the only inherently serial part is the first partition. I tried parallelizing a quick sort by, after each partition, sorting the two subarrays in parallel.  In simplified pseudocode:</p>
  
  <pre><code>// I tweaked this number a bunch.  Anything smaller than this and the 
  // overhead is smaller than the parallelization gains.
  const  smallestToParallelize = 500; 
  
  void quickSort(T)(T[] array) {
      if(array.length &lt; someConstant) {
          insertionSort(array);
          return;
      }
  
      size_t pivotPosition = partition(array);
  
      if(array.length &gt;= smallestToParallelize) {
          // Sort left subarray in a task pool thread.
          auto myTask = taskPool.execute(quickSort(array[0..pivotPosition]));
          quickSort(array[pivotPosition + 1..$]);
          myTask.workWait();
      } else {
          // Regular serial quick sort.
          quickSort(array[0..pivotPosition]);
          quickSort(array[pivotPosition + 1..$]);
      }
  }
  </code></pre>
  
  <p>Even for very large arrays, where the time the first partition takes is negligible, I can only get about a 30% speedup on a dual core, compared to a purely serial version of the algorithm.  I'm guessing the bottleneck is shared memory access.  Any insight on how to eliminate this bottleneck or what else the bottleneck might be?</p>
  
  <p>Edit:  My task pool has a fixed number of threads, equal to the number of cores in the system minus 1 (since the main thread also does work).  Also, the type of wait I'm using is a work wait, i.e. if the task is started but not finished, the thread calling <code>workWait()</code> steals other jobs off the pool and does them until the one it's waiting on is done.  If the task isn't started, it is completed in the current thread.  This means that the waiting isn't inefficient.  As long as there is work to be done, all threads will be kept busy.</p>