ALGORITHM COMPARISON
好的选择，从理解差异开始。
复杂度相似，不代表适用场景相同。比较两个算法的保证、代价与前提，再做选择。
VS
| 比较维度 | Quick Sort | Merge Sort |
|---|---|---|
| 典型时间 / 平均 | O(n log n) | O(n log n) |
| 最坏 / 实现差异 | O(n²) | O(n log n) |
| 辅助空间 | 平均 O(log n) 栈；最坏 O(n) | 数组实现 O(n) |
| 稳定性 | 否 | 是（相等时先取左侧） |
| 核心结构 | 原地分区 + 递归 | 分治 + 有序合并 |
| 适用场景 | 内存数组排序，通常局部性较好 | 稳定排序、外部排序、链表排序 |
为什么它们都有存在价值？
快速排序通过原地分区减少数组辅助存储，常有良好的缓存局部性；归并排序提供稳定性和最坏 O(n log n) 时间保证，也适合合并磁盘中的有序段。工程选择取决于数据布局、稳定性需求、额外内存与最坏情况约束。
Quick Sort 的边界
固定基准与大量重复值可能使分区失衡；工程常结合随机化、三路分区或内省策略。
固定基准与大量重复值可能使分区失衡；工程常结合随机化、三路分区或内省策略。
Merge Sort 的边界
数组版需要合并缓冲区；链表实现有不同的空间特征。
数组版需要合并缓冲区；链表实现有不同的空间特征。