std::list::sort(): Why the Shift to a Top-Down Merge Sort?

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

The switch from a bottom-up to a top-down merge sort in std::list<>::sort() arose to address the need for more robust and exception-safe sorting. The previous implementation used an array of internal lists, but this could encounter issues due to the introduction of non-default-constructible and stateful allocators in VS2015.

To circumvent this, Microsoft's Stephan T. Lavavej suggested using iterators to keep track of run boundaries within the original linked list. This allows for the use of std::list::splice to move nodes within the list during merge operations, ensuring exception safety. While this change improves robustness, it does incur a performance cost, as scanning through a linked list to find the midpoint can be inefficient.

However, in the Visual Studio 2022 update, Microsoft enhanced the top-down implementation by switching to a more efficient recursive strategy where integer sizes are simply halved rather than iterating through the list. This modification preserves the benefits of exception safety and avoids the performance penalty of repeated calls to std::next.

As an alternative to the top-down approach, some developers have proposed using a bottom-up merge sort with iterators, as introduced earlier in this document. This approach also uses iterators but operates in a bottom-up fashion, eliminating the need to scan through the list to find the midpoint. The specific implementation depends on the size of the list and the distribution of nodes, with trade-offs between time and space complexity.

While the top-down merge sort remains the default in std::list<>::sort(), the modified implementation in VS2022 aims to provide a balance of efficiency and exception safety. Developers may explore alternative implementations, such as bottom-up merge sort with iterators, depending on the specific requirements of their application.

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