为什么稳定且原地的通用排序很难实现？
简化版
稳定排序要求相等元素保持原相对顺序，原地排序要求额外空间很少。
这两个目标很难同时满足。归并排序稳定，但通常需要 O(n) 辅助数组；堆排序原地，但不稳定；快速排序常见实现原地，但也不稳定。
稳定且原地的通用排序不是做不到，而是实现复杂、常数大，所以标准库更常在稳定性、空间和速度之间做取舍。
详细版
排序常见目标包括：
| 目标 | 含义 |
|---|---|
| 稳定 | 相等 key 的相对顺序不变 |
| 原地 | 额外空间 O(1) 或很小 |
| 快 | 时间接近 O(n log n) |
| 简单 | 容易实现和维护 |
想同时满足这些目标很难。
稳定 + 简单 -> 归并排序，但空间 O(n)
原地 + O(n log n) -> 堆排序，但不稳定
平均快 + 原地 -> 快排，但不稳定且最坏可能退化面试中要说明：这是工程取舍，不只是算法表格背诵。
完整版教学
1. 稳定性要求什么
稳定性要求相等元素保持原来的相对顺序。
例如：
(score=90, name=A)
(score=90, name=B)按 score 排序后，A 仍然要在 B 前面。
这对多关键字排序很重要，比如先按姓名排序，再按成绩稳定排序。
2. 原地排序要求什么
原地排序通常指额外空间很小，常见说法是 O(1)。
它希望主要在原数组内部交换、移动元素。
这对内存敏感场景有意义，但会限制算法能做的操作。
稳定性要求“别打乱相等元素”，原地性要求“别借太多额外空间”，两者天然有张力。
3. 归并排序为什么稳定但不够原地
归并排序稳定的关键在合并两个有序段。
合并时，如果左右两边元素相等，先取左边元素，就能保持稳定性。
但简单高效的合并通常需要辅助数组：
temp = merge(left, right)
copy temp back这个辅助数组带来 O(n) 额外空间。
4. 堆排序为什么原地但不稳定
堆排序主要通过堆顶和末尾交换来把最大值放到后面。
这种长距离交换可能让相等元素跨越彼此。
例如两个相等 key 的元素 A 和 B，在建堆和下沉过程中可能被交换到相反顺序。
所以堆排序虽然额外空间小，但默认不稳定。
5. 快排为什么通常不稳定
快速排序 partition 时会交换元素。
相等元素可能被换到不同位置，原始相对顺序不受保护。
即使三路快排把等于 pivot 的元素集中起来，也不天然保证稳定，因为交换过程仍可能打乱顺序。
要让快排稳定，通常需要额外空间或更复杂的 partition。
6. 稳定原地排序为什么复杂
稳定原地合并需要在数组内部移动元素，同时保留相等元素顺序。
这可能涉及：
- 块划分；
- 旋转数组区间；
- 原地归并；
- 复杂缓冲区管理；
- 大量边界处理。
理论上存在稳定原地的 O(n log n) 算法，但工程实现难度和常数都不小。
7. 标准库怎么取舍
很多标准库会根据语言和场景选择不同策略。
| 需求 | 常见选择 |
|---|---|
| 稳定排序 | TimSort、归并类 |
| 原始类型快速排序 | 双轴快排或 IntroSort |
| 最坏复杂度保护 | IntroSort |
| 近乎有序数据 | TimSort 很有优势 |
标准库看重的不只是理论复杂度，还包括真实数据分布、常数、内存和安全退化。
8. 常见误区与追问
- 误区：稳定和原地只是两个独立标签。 它们会互相牵制，同时满足往往很难。
- 误区：归并排序一定不能原地。 理论上可做原地归并，但简单高效实现通常用
O(n)空间。 - 误区：堆排序原地所以更适合所有场景。 堆排序不稳定，缓存局部性和常数也未必最好。
- 追问：为什么相等元素会被快排打乱？ partition 中的交换不保留相等元素原始顺序。
- 追问：标准库为什么不都用稳定原地排序？ 实现复杂、常数大，工程上常选择更均衡的方案。