归并排序是怎样实现的？为什么是稳定的？
先自己想一想，再看参考要点
参考要点
- 把数组分成两部分分别排序，再把两个有序的部分归并成一个
- 归并时用辅助数组，两个指针分别从两部分的开头比较，每次取较小的一个放回原数组
- 自顶向下的写法每次对半分并递归，递归共 logN 层，每一层的归并合起来处理 N 个元素，复杂度 O(NlogN)
- 自底向上的写法先归并微型数组，再成对归并得到的数组，不需要递归
- 两部分的元素相等时先取左侧的，相等元素保持原来的相对顺序，所以是稳定的，JDK 对引用类型排序用的 TimSort 就是归并排序的改进版本