title: Problem understanding code from C++: Concurrency in Action
body: <p>I'm studying Concurrency in Action (first edition, C++11) and I have some problems understanding part of code from chapter 8, page 228, in which the autor shows a multithreaed-version of QuickSort in the context of dividing data recursively.</p>
  <p>The whole code  is:</p>
  <pre><code>template&lt;typename T&gt;
  struct sorter
  {
      struct chunk_to_sort
      {
          std::list&lt;T&gt; data;
          std::promise&lt;std::list&lt;T&gt; &gt; promise;
      };
  
      thread_safe_stack&lt;chunk_to_sort&gt; chunks;  //this is a thread-safe stack explained somewhere else
      std::vector&lt;std::thread&gt; threads;
      unsigned const max_thread_count;
      std::atomic&lt;bool&gt; end_of_data;
  
      sorter():
          max_thread_count(std::thread::hardware_concurrency()-1),
          end_of_data(false)
      {}
  
      ~sorter()
      {
          end_of_data=true;
          for(unsigned i=0;i&lt;threads.size();++i)
          {
              threads[i].join();
          }
      }
  
      void try_sort_chunk()
      {
          boost::shared_ptr&lt;chunk_to_sort &gt; chunk=chunks.pop();
          if(chunk)
          {
          sort_chunk(chunk);
          }
      }
  
      std::list&lt;T&gt; do_sort(std::list&lt;T&gt;&amp; chunk_data)
      {
          if(chunk_data.empty())
          {
              return chunk_data;
          }
          std::list&lt;T&gt; result;
          result.splice(result.begin(),chunk_data,chunk_data.begin());
          T const&amp; partition_val=*result.begin();
  
          typename std::list&lt;T&gt;::iterator divide_point=
              std::partition(chunk_data.begin(),chunk_data.end(),
                             [&amp;](T const&amp; val){return val&lt;partition_val;});
  
          chunk_to_sort new_lower_chunk;
          new_lower_chunk.data.splice(new_lower_chunk.data.end(),
                                      chunk_data,chunk_data.begin(),
                                      divide_point);
  
          std::future&lt;std::list&lt;T&gt; &gt; new_lower=
              new_lower_chunk.promise.get_future();
          chunks.push(std::move(new_lower_chunk));
          if(threads.size()&lt;max_thread_count)
          {
              threads.push_back(std::thread(&amp;sorter&lt;T&gt;::sort_thread,this));
          }
  
          std::list&lt;T&gt; new_higher(do_sort(chunk_data));
  
          result.splice(result.end(),new_higher);
          while(new_lower.wait_for(std::chrono::seconds(0)) !=
                std::future_status::ready)
          {
              try_sort_chunk();
          }
  
          result.splice(result.begin(),new_lower.get());
          return result;
      }
  
      void sort_chunk(boost::shared_ptr&lt;chunk_to_sort &gt; const&amp; chunk)
      {
          chunk-&gt;promise.set_value(do_sort(chunk-&gt;data));
      }
  
      void sort_thread()
      {
          while(!end_of_data)
          {
              try_sort_chunk();
              std::this_thread::yield();
          }
      }
  };
  
  template&lt;typename T&gt;
  std::list&lt;T&gt; parallel_quick_sort(std::list&lt;T&gt; input)
  {
      if(input.empty())
      {
          return input;
      }
      sorter&lt;T&gt; s;
      return s.do_sort(input);
  }
  </code></pre>
  <p><strong>The part I do not get the logic of</strong> is inside the function template do_sort, that is:</p>
  <pre><code>    chunk_to_sort new_lower_chunk;
      new_lower_chunk.data.splice(new_lower_chunk.data.end(),
                                  chunk_data,chunk_data.begin(),
                                  divide_point);
  
      std::future&lt;std::list&lt;T&gt; &gt; new_lower=
          new_lower_chunk.promise.get_future();
      chunks.push(std::move(new_lower_chunk));
      if(threads.size()&lt;max_thread_count)
      {
          threads.push_back(std::thread(&amp;sorter&lt;T&gt;::sort_thread,this));
      }
  
      std::list&lt;T&gt; new_higher(do_sort(chunk_data));
  
      result.splice(result.end(),new_higher);
      while(new_lower.wait_for(std::chrono::seconds(0)) !=
            std::future_status::ready)
      {
          try_sort_chunk();
      }
  
      result.splice(result.begin(),new_lower.get());
      return result;
  </code></pre>
  <p>I get the single instructions.
  I do not get the whole picture, namely how and where the data are recursively divided and ordered by different threads.</p>