Why the Sudden Switch to Top-Down Strategy in std::list::sort()?

In Visual Studio 2015 (VS2015), Microsoft switched the sorting strategy of std::list::sort() from the traditional bottom-up Merge Sort to a top-down approach. This change eliminated the use of an internal array of lists and adopted iterators to track sorted run boundaries within the original list.

Reasons for the Change

Stephan T. Lavavej, the developer of the top-down approach, cited the need to avoid memory allocation and the construction of non-default allocators. VS2015 introduced allocators that were no longer default constructible and stateful, which posed issues when using the previous bottom-up approach.

Implementation of Top-Down Approach

The top-down approach utilizes a recursive algorithm that recursively divides the list into halves until it reaches base cases where the lists are empty or contain a single element. The function _Sort partitions the list into three segments: left run, right run, and the end iterator. The merge logic is performed using std::list::splice to move nodes within the original list, maintaining exception safety.

Performance Considerations

While the top-down approach addresses the memory allocation concerns, it comes with a performance penalty compared to the original bottom-up Merge Sort. For large lists with scattered nodes, the top-down approach suffers from increased cache misses, resulting in slower execution times. In such cases, it may be faster to move the list to an array or vector, sort it, and create a new list from the sorted array or vector.