std::list::sort 用了什么算法？为什么速度这么快？

std::list::sort 的速度之所以令人印象深刻，主要归功于它所使用的特定排序算法以及 `std::list` 本身的数据结构特性。

std::list::sort 的背后算法：合并排序 (Merge Sort)

在 C++ 标准库的实现中，`std::list::sort` 通常使用的是合并排序（Merge Sort）算法。这是非常关键的一点，因为合并排序在链表排序方面有着天然的优势。

为什么是合并排序？

我们先来理解一下合并排序的基本原理：

1. 分而治之 (Divide and Conquer): 合并排序的核心思想是将待排序的列表不断地分成更小的子列表，直到每个子列表只包含一个元素（单个元素天然有序）。
2. 合并 (Merge): 然后，它将这些小的、有序的子列表两两合并，每次合并都生成一个更大的有序列表。这个过程持续进行，直到所有的子列表都被合并成一个完整的有序列表。

合并排序在链表上的优势：

插入和删除的成本低: `std::list` 是一个双向链表。这意味着在链表中插入或删除一个元素只需要 O(1) 的时间复杂度，前提是你已经有了指向要插入/删除位置的迭代器。不需要像数组那样进行元素的移动。
避免了随机访问的开销: 数组或其他基于随机访问的数据结构在排序时（例如快速排序）可能会频繁地访问不同位置的元素。链表恰恰相反，访问元素需要从头开始遍历，这在随机访问时是劣势。但合并排序在“合并”阶段，只需要顺序地比较和链接节点，不需要跳跃式的随机访问，因此链表的顺序访问特性反而成了优点。
稳定性: 合并排序是一种稳定排序算法。这意味着如果两个元素具有相同的值，它们在排序后的相对位置与它们在排序前的相对位置相同。这对于某些需要保留原始顺序的场景非常重要。
时间复杂度: 合并排序在所有情况下（最好、最坏、平均）的时间复杂度都是 O(n log n)。这是效率非常高的一个指标，尤其对于大型数据集。

std::list::sort 的具体实现细节：

虽然标准规定了行为，但具体实现可能略有不同。不过，一个常见的且高效的 `std::list::sort` 实现会采用以下方式：

1. 切分链表: 它会找到链表的中间点，并将链表分割成两个大致相等的部分。这个过程同样是 O(n) 的，因为需要遍历链表找到中间节点。
2. 递归排序: 对这两个子链表分别进行递归排序。
3. 合并有序子链表: 这是最关键的一步。它会创建一个新的空链表（或者复用节点来构建），然后从两个已排序的子链表头部开始，逐个比较元素。较小的元素会被取出并添加到新链表的末尾。这个过程一直持续，直到其中一个子链表为空。最后，将另一个子链表中剩余的元素全部添加到新链表末尾。
关键点： 在合并过程中，不需要移动链表中的实际数据。只需要修改节点的 `next` 和 `prev` 指针。这正是链表进行插入/删除的高效性所在。一个节点被“移动”到新链表中的操作，仅仅是改变了它的前后节点的链接。

为什么说它“速度快”？

“速度快”是一个相对的概念，但对于 `std::list` 而言，`sort` 的速度快主要体现在：

与其他列表排序方法相比: 如果你尝试手动实现一个插入排序或冒泡排序来排序 `std::list`，你会发现它们的性能非常糟糕（O(n^2)）。合并排序的 O(n log n) 明显优于这些。
与基于数组的 O(n log n) 排序相比: 例如快速排序在数组上的平均时间复杂度也是 O(n log n)。但是，快速排序在数组上的实现，其常数因子通常比链表的合并排序要小一些，因为它能更好地利用缓存。然而，`std::list::sort` 的优势在于它不需要额外的内存来存储临时数据（如许多数组排序算法需要一个辅助数组），因为它直接在原链表上操作（通过重新链接节点）。
避免了 O(n) 的复制或移动: 想象一下，如果要对一个数组进行合并排序，你可能需要一个额外的数组来存放合并后的结果，然后将结果复制回原数组。对于 `std::list`，通过直接修改节点的指针，可以避免这种昂贵的数据复制或移动操作。

总结：

`std::list::sort` 之所以表现出色，是因为它巧妙地结合了合并排序算法的优秀时间复杂度 (O(n log n)) 与 `std::list` 数据结构本身在插入和删除操作上的低成本特性。它不需要额外的空间进行排序（与许多需要辅助空间的排序算法不同），并且避免了在排序过程中对大量数据进行昂贵的移动。这使得它成为排序 `std::list` 的理想选择。

这是SGISTL List 的实现，看sort方法

http://www. sgi.com/tech/stl/stl_li st.h