归并排序
把列表分成两半，分别排好，再把排好的两半合并成一个排好的列表。
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- 是
- 否
最佳：输入对这个算法最容易时，时间随列表大小 n 增长的方式。
平均：时间随 n 的一般增长。n² 表示值的个数翻倍时耗时约为四倍；n log n 增长得慢得多。
最差：最难的输入下的增长。适合速度绝不能下降的场合。
内存：除列表外还需要多少额外内存。1 表示几个变量，n 表示一份列表副本。
稳定：两个相等的值保持原来的顺序。按记录的某个字段排序时很重要。
无需额外内存：直接在列表内部排序，不用第二个列表。
- 比较中
- 移动中
- 已就位
试试看： 选一个重复值较多的列表。两个值相等时，先取左半边的那个，所以相等的值会保持原来的顺序。
工作原理
不断把列表对半分，直到每块只剩一个值，这时它自然是排好的。然后两块两块地合并：比较两块最前面的值，取较小的那个，如此反复。动画中升起的那一行，就是合并时用到的额外空间。
适用场合
适合最坏情况下也要保持快速，并且相等的值必须保持原来顺序的场合。Python 和 Java 都使用归并排序的某种变体。缺点是需要额外内存。