Why Did Microsoft Switch to a Top-Down Merge Sort in std::list::sort()?

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

Despite the long-standing use of a bottom-up Merge Sort approach in std::list<>::sort(), Microsoft's Visual Studio 2015 made a shift to a surprisingly inefficient recursive implementation of top-down Merge Sort. This change raises questions about the underlying motivations.

Initially, it was assumed that Microsoft had a compelling reason to switch to a less efficient approach, especially given the introduction of non-default-constructible and stateful allocators in VS2015. However, upon further investigation, it was discovered that the original bottom-up Merge Sort algorithm could be modified to work with iterators.

Microsoft's Top-Down Approach

Microsoft's top-down implementation uses a recursive approach to split the list in half at each level of recursion. The apparent reason for this is to avoid memory allocation and exception safety concerns. Instead of creating an array of lists to store sorted runs, they use iterators to keep track of the run boundaries within the original list.

While this approach may prevent memory allocation issues, it introduces an inefficiency in the form of accessing the midpoint of the list in each recursive call, potentially leading to a slower execution time.

Alternative Bottom-Up Approach

As an alternative, other developers have proposed a modified version of the bottom-up Merge Sort algorithm that uses iterators instead of an array of lists. This approach involves creating an array of iterators, where each entry represents the starting point of a sorted run. As the list is scanned, nodes are merged into these runs until a single sorted list is obtained.

This method offers both speed and memory efficiency, outperforming top-down Merge Sort by approximately 40-50% on lists with scattered nodes in memory.

Conclusion

The reasons for Microsoft's switch to top-down Merge Sort remain somewhat unclear. While memory allocation and exception safety concerns may have influenced the decision, it's important to note that these issues can be addressed with alternative approaches that maintain higher efficiency. The choice of a less efficient algorithm suggests that Microsoft may have prioritized stability and exception handling over performance.

The above is the detailed content of Why Did Microsoft Switch to a Top-Down Merge Sort in std::list::sort()?. For more information, please follow other related articles on the PHP Chinese website!