title: `std::list<>::sort()` - why the sudden switch to top-down strategy?
body: <p>I remember that since the beginning of times the most popular approach to implementing <code>std::list&lt;&gt;::sort()</code> was the classic Merge Sort algorithm implemented in <a href="https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists" rel="noreferrer">bottom-up fashion</a> (see also <a href="https://stackoverflow.com/questions/6728580/what-makes-the-gcc-stdlist-sort-implementation-so-fast">What makes the gcc std::list sort implementation so fast?</a>). </p>
  
  <p>I remember seeing someone aptly refer to this strategy as "onion chaining" approach.</p>
  
  <p>At least that's the way it is in GCC's implementation of C++ standard library (see, for example, <a href="https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-api-4.6/a00925_source.html#l00355" rel="noreferrer">here</a>). And this is how it was in old Dimkumware's STL in MSVC version of standard library, as well as in all versions of MSVC all the way to VS2013. </p>
  
  <p>However, the standard library supplied with VS2015 suddenly no longer follows this sorting strategy. The library shipped with VS2015 uses a rather straightforward recursive implementation of <em>top-down</em> Merge Sort. This strikes me as strange, since top-down approach requires access to the mid-point of the list in order to split it in half. Since <code>std::list&lt;&gt;</code> does not support random access, the only way to find that mid-point is to literally iterate through half of the list. Also, at the very beginning it is necessary to know the total number of elements in the list (which was not necessarily an O(1) operation before C++11).</p>
  
  <p>Nevertheless, <code>std::list&lt;&gt;::sort()</code> in VS2015 does exactly that. Here's an excerpt from that implementation that locates the mid-point and performs recursive calls</p>
  
  <pre><code>...
  iterator _Mid = _STD next(_First, _Size / 2);
  _First = _Sort(_First, _Mid, _Pred, _Size / 2);
  _Mid = _Sort(_Mid, _Last, _Pred, _Size - _Size / 2);
  ...
  </code></pre>
  
  <p>As you can see, they just nonchalantly use <code>std::next</code> to walk through the first half of the list and arrive at <code>_Mid</code> iterator.</p>
  
  <p>What could be the reason behind this switch, I wonder? All I see is a seemingly obvious inefficiency of repetitive calls to <code>std::next</code> at each level of recursion. Naive logic says that this is <em>slower</em>. If they are willing to pay this kind of price, they probably expect to get something in return. What are they getting then? I don't immediately see this algorithm as having better cache behavior (compared to the original bottom-up approach). I don't immediately see it as behaving better on pre-sorted sequences.</p>
  
  <p>Granted, since C++11 <code>std::list&lt;&gt;</code> is basically required to store its element count, which makes the above slightly more efficient, since we always know the element count in advance. But that still does not seem to be enough to justify the sequential scan on each level of recursion.</p>
  
  <p>(Admittedly, I haven't tried to race the implementations against each other. Maybe there are some surprises there.)</p>