list::sort在msvc中使用什么排序算法？

Question

据我所知，std::sort通常使用introsort。

但是，当我在这里阅读这篇文章时，std::list::sort说合并排序很容易实现，并且没有提到要使用哪种算法。

msvc是否使用合并排序？

Answer 1

在Visual Studio 2015中，算法从自下而上改为自上而下的合并排序。更改的作者指出，这样做是为了处理没有默认分配器的列表，但在声明列表时，使用get_allocator() (修复方法将为列表数组中的26个元素中的每个元素包含一个get_allocator()实例)可以很容易地处理该问题。

更新- Visual Studio版本的关键变化是从使用列表数组切换到使用存储在堆栈上的迭代器，并通过拼接进行合并，采用自顶向下的方法。迭代器避免了没有默认分配器的问题。以及通过拼接进行合并，这防止了在比较或其他问题抛出异常时列表中的数据丢失。然而，事实证明，使用迭代器数组和通过拼接逻辑使用本质上相同的合并的自底向上方法是可能的，尽管直到最近我才尝试实现基于迭代器的自底向上合并排序。下面第一个链接中的讨论现在包括使用迭代器的示例自下而上合并排序代码。

作者确实注意到，切换到自上而下意味着性能下降，但他正确地指出，如果性能是一个问题，那么在大多数情况下，将列表移动到向量，对向量进行排序，然后从排序后的向量创建列表会更快。尽管如此，大多数STL函数都是合理优化的，因此一些人的论点是，可以修复早期的自下而上方法，以处理没有默认的分配器列表。

虽然作者没有提到这一点，但在下面的链接中的讨论中，也指出了如果用户比较函数抛出异常，自顶向下的实现避免了数据丢失。然而，如果比较函数抛出异常，std::stable_sort()等其他STL函数将丢失数据，我的印象是，用户提供的函数创建的异常不是VS STL的优先级，应该在调试版本中捕获。

std::list<>::sort() - why the sudden switch to top-down strategy?

Wiki文章包括链接列表的自上而下和自下而上合并排序的示例：

https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

Answer 2

在Visual Studio2017中可以看到的<list>头文件中，您将找到_Sort的函数模板，该模板遵循merge sort。

您还可以找到merge函数的几个重载和函数模板。