Why did Visual Studio 2015 switch from bottom-up to top-down merge sort for std::list::sort()?

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

In Visual Studio 2015, the implementation of std::list::sort() underwent a significant change from the classic bottom-up merge sort to a top-down merge sort. This shift introduced an apparent inefficiency by requiring the midpoint of the list to be found for each level of recursion.

Reasons for the Change:

However, as documented in the update provided, Microsoft made optimizations to preserve the no memory allocation and exception safety fixes that motivated the initial change to using iterators. Specifically, the recursive implementation:

• Uses an efficient merge sort that divides the list by 2 at each level of recursion, instead of scanning the list.
• Reverts back to using pointers instead of iterators, potentially improving performance.
• Implements splice logic to improve the merging of multiple nodes at a time.

Comparison to Bottom-Up Merge Sort:

Despite the optimizations, the top-down approach still has the potential to be slower than the bottom-up merge sort when dealing with large, scattered linked lists due to increased cache misses.

Alternative Implementation:

An alternative implementation is provided that retains the bottom-up merge sort approach while utilizing iterators instead of an array of lists. This approach aims to avoid the performance hit of always having to find the list's midpoint during recursion.

Conclusion:

The switch to a top-down merge sort in Visual Studio 2015 was not made on a whim. Microsoft implemented optimizations to address the potential inefficiencies, while retaining the benefits of exception safety and reducing memory allocation. However, for large, sparsely populated linked lists, a bottom-up merge sort approach may still provide better performance.

The above is the detailed content of Why did Visual Studio 2015 switch from bottom-up to top-down merge sort for std::list::sort()?. For more information, please follow other related articles on the PHP Chinese website!