title: parallel quick sort outdone by single threaded quicksort
body: <p>I've been reading the book C++ concurrency in action, here is the example in the book using futures to implement parallel quick sort.</p>
  
  <p>But I found this function is more than twice slower than the single threaded quick sort function without using any asynchronous facilities in c++ standard library.
  Tested with g++ 4.8 and visual c++ 2012.</p>
  
  <p>I used 10M random integers to test, and in visual c++ 2012,this function spawned 6 threads in total to perform the operation in my quad core PC.</p>
  
  <p>I am really confused about the performance. Any body can tell me why?</p>
  
  <pre><code>template&lt;typename T&gt;
  std::list&lt;T&gt; parallel_quick_sort(std::list&lt;T&gt; input)
  {
      if(input.empty())
      {
          return input;
      }
      std::list&lt;T&gt; result;
      result.splice(result.begin(),input,input.begin());
      T const&amp; pivot=*result.begin();
      auto divide_point=std::partition(input.begin(),input.end(),
          [&amp;](T const&amp; t){return t&lt;pivot;});
      std::list&lt;T&gt; lower_part;
      lower_part.splice(lower_part.end(),input,input.begin(),
          divide_point);
      std::future&lt;std::list&lt;T&gt; &gt; new_lower(
          std::async(&amp;parallel_quick_sort&lt;T&gt;,std::move(lower_part)));
      auto new_higher(
          parallel_quick_sort(std::move(input)));
      result.splice(result.end(),new_higher);
      result.splice(result.begin(),new_lower.get());
      return result;
  }
  </code></pre>