Q：什么是归并排序？
A：它是建立在归并操作上的一种有效的排序算法；是采用分治法的一个非常典型的应用；是一种稳定的

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

优点？它能保证将任意长度为 N 的数组排序所需时间和 NlogN 成正比；

缺点？所需的额外空间和 N 成正比。

Q：为什么需要原地归并？
A：因为用归并将一个大数组排序时，需要进行多次归并，而且每次归并会都创建一个新数组来存储排序结果会带来问题。

Q：原地归并实现了什么？
A：可以先将前半部分排序，再将后半部分排序，然后数组中移动元素而不需要使用额外的空间。（将两个有序的数组归并为一个有序的数组）

Q：如何实现归并？
A：创建一个适当大小的数组，然后将两个输入数组中的元素一个个从小到大方法这个数组中。

代码实现
根据排序算法类的模板实现选择排序（提醒：点蓝字查看详情）

由于以上的原地归并只能将两个有序的数组归并成一个有序的数组，所以得基于原地归并的抽象去实现一种递归归并。

要对子数组 arr[lo…hi] 进行排序，先将它分为 arr[lo…mid] 和 arr[mid+1…hi] 两部分，分别通过递归调用将它们单独排序，最后将有序的子数组归并为最终的排序结果。

Q：为什么它能将正确的排序？
A：如果它能将两个子数组排序，那么它就可以通过归并两个子数组来将整个数组排序。

运行轨迹<