title: Running time of std::list parallel quick sort
body: <p>I follow the quick sort implementation in Chapter 4 of 《C++ Concurrency in Action》,and then comparing the single-threaded and multi-threaded runtimes, the code is as follows:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>int main()
  {
    int num_elements = 10000;
      list&lt;int&gt; input(num_elements);
      // generate random numbers
      std::generate(input.begin(), input.end(),
                    []{ return std::rand();});
  
    {
      auto start = std::chrono::steady_clock::now();
      auto sorted = sequential_quick_sort(input); // single-thread
      auto end = std::chrono::steady_clock::now();
      cout &lt;&lt; "sequence :" &lt;&lt; std::chrono::duration&lt;double, std::milli&gt;(end-start).count() &lt;&lt; endl;
    }
  
    {
      auto start = std::chrono::steady_clock::now();
      auto sorted = parallel_quick_sort(input);   // multi-thread (two thread)
      auto end = std::chrono::steady_clock::now();
      cout &lt;&lt; "parallel :" &lt;&lt; std::chrono::duration&lt;double, std::milli&gt;(end-start).count() &lt;&lt; endl;
    }
  
    return 0;
  }
  </code></pre>
  
  <p>output:</p>
  
  <pre><code>sequence :15.1315
  parallel :14.6983
  </code></pre>
  
  <p>Output shows that multi-thread has no better performance. But when I change the code as follows:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>int main()
  {
    int num_elements = 10000;
  
    {
        list&lt;int&gt; input(num_elements);
        // generate random numbers
        std::generate(input.begin(), input.end(),
                      []{ return std::rand();});
  
      auto start = std::chrono::steady_clock::now();
      auto sorted = sequential_quick_sort(input); // single-thread
      auto end = std::chrono::steady_clock::now();
      cout &lt;&lt; "sequence :" &lt;&lt; std::chrono::duration&lt;double, std::milli&gt;(end-start).count() &lt;&lt; endl;
    }
  
    {
        list&lt;int&gt; input(num_elements);
        // generate random numbers
        std::generate(input.begin(), input.end(),
                      []{ return std::rand();});
  
      auto start = std::chrono::steady_clock::now();
      auto sorted = parallel_quick_sort(input);   // multi-thread (two thread)
      auto end = std::chrono::steady_clock::now();
      cout &lt;&lt; "parallel :" &lt;&lt; std::chrono::duration&lt;double, std::milli&gt;(end-start).count() &lt;&lt; endl;
    }
  
    return 0;
  }
  </code></pre>
  
  <p>output:</p>
  
  <pre><code>sequence :15.0191
  parallel :7.93202
  </code></pre>
  
  <p>Multi-thread version is twice as fast as the single-thread version. 
  But why?</p>