对基本有序的序列排序算法
quicksort 是基于比较的排序中表现最好的算法，它在大多数情况下都能接近时间复杂度 O(n log n) ，所以 qsort() 也是 C 标准库中排序的默认实现。但是，quicksort 是非稳定排序，即当原始序列中出现相同的元素时，经过 qsort ，这些相同元素的次序可能被调整。即两个 key 相同的元素，经过排序可能调换次序。
在某些场合，我们希望排序是稳定 stable 的。因为元素的 key 相同，但元素本身可以不相同。这些有着相同 key 的元素一开始以某种次序放入序列，我们不希望对 key 排序后，打乱原有的次序。当需要稳定性时，还有许多经典排序算法可供选择，例如插入排序，它非常简单，每次从无序序列中选择一个元素和有序序列的最后一个元素比较，要么追加在最后，要么向前依次比较，直到找到合适的位置插入。对已经有序的序列，插入排序的时间复杂度为 O(n) ，但对于逆序的序列，它会退化到 O(n^2) ，因为每个元素都要和之前所有元素比较一次，插入到最前。所以插入排序对于非特定场景（无特定规律的数据）的平均时间复杂度接近 O(n^2) 超过快速排序的 O(n log n) 。
但需要注意，光看大 O 时间复杂度是不够的。在 n 很小的时候，对实际开销影响更大的并非算法复杂度。因为复杂度是基于执行算法中每个单步操作的数量估算的，忽略了操作本身的时间差异。而 n 很小时，单个操作的开销占比就变大了。所以在 n 很小时，简单的算法每个操作都更短，对 CPU cache 也更友好，导致实际的总时间开销也越少。大部分排序算法的实现都选择在 n 很小时退化成插入排序。
对无规律数据集，基于比较的排序算法的理论极限是 O (n log n)。因为你需要至少对所有元素做一次比较，采用二分的形式分而治之是最好的方法，不断二分数据集的深度大致为 log n 。归并排序 merge sort 直观的体现了这个想法，它把数据不断对分，展开为一个完全平衡的二叉树，然后从叶节点逐级向根节点调整次序并合并，一路执行到根节点，就可以完成排序。所以它可以严格（即使在最坏情况）做到 O (n log n) 。或者这么看，合并两个有序序列只需要扫描两个序列各一遍，每次都挑出两个序列头部更考前的元素，插入新序列，就能得到合并后的有序序列。假设一共有 128 个元素，不断对分，就能分成 64 组元素每组 2 个。这两个元素调整位置合并成 32 组 4 元组，再继续为 16 组 8 元组，等等。
显然，merge sort 是很容易做到 stable ，但缺点是它难以在原地 in-place 排序，需要额外的空间。这导致实际实现时，需要额外的内存复制。在大多数要求 in-place 排序（大多数 sort api 都是这样）的场合，比 quicksort 要慢，且需要额外的运行空间。
但在真实世界的应用场合，大多数需要排序的数据并非毫无规律。针对有规律的数据排序就可以在工程上针对规律做出改进。一个普遍的规律是：往往需要排序的数据本身就是基本有序的，至少很多片段是局部有序的。因为你很难一次性获得海量的完全随机的数据集。数据都是逐步变多的，如果它们之前的片段是有序的，在整合到一起后，大部分还保持着次序；或者是原有的次序经过少量的调整，破坏了局部的次序。针对这点，就可以对 merge sort 做大幅改进。python 最早的版本直接封装 C 的 qsort() 实现排序，但随着 stable sort 的需求日益增加，在 2002 年 Tim Peters 针对这类情况改进了 merge sort 算法，最终成为 python 排序算法的标准实现。这是一个混合排序算法，一开始并未正式命名，但随着它作为一个比 merge sort 更能适应现实数据集的算法被引入 java 等其它语言的标准库，大家就用第一次工程实现者的名字命名为 timsort 。btw , 它的核心想法并不新，在 Knuth 的计算机算法艺术第三卷的排序算法中就有提到。
