为什么 std::list::sort() 中突然切换到自上而下策略？

在 Visual Studio 中2015年（VS2015），微软将std::list::sort()的排序策略从传统的自下而上的归并排序转换为自上而下的方法。此更改消除了内部列表数组的使用，并采用迭代器来跟踪原始列表内的排序运行边界。

更改原因

Stephan T. Lavavej自上而下方法的开发人员指出需要避免内存分配和非默认分配器的构造。 VS2015 引入了不再默认可构造和有状态的分配器，这在使用以前的自下而上方法时带来了问题。

自上而下方法的实现

顶部-down 方法利用递归算法，将列表递归地分成两半，直到达到列表为空或包含单个元素的基本情况。函数 _Sort 将列表分为三段：左游、右游和结束迭代器。合并逻辑是使用 std::list::splice 来移动原始列表内的节点，从而保持异常安全。

性能注意事项

而自顶向下该方法解决了内存分配问题，但与原始的自下而上的归并排序相比，它会带来性能损失。对于节点分散的大型列表，自上而下的方法会受到缓存未命中增加的影响，从而导致执行时间变慢。在这种情况下，将列表移动到数组或向量，对其进行排序，然后从排序后的数组或向量创建新列表可能会更快。