归并排序（merge sort）是高效的基于比较的稳定排序算法。和快速排序一样，也采用分治思想，先进行序列划分，再进行元素的有序合并。
归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为，空间复杂度为
归并排序可以只使用的辅助空间，但为便捷通常使用与原数组等长的辅助数组
合阶段
将两个已经有序的子序列合并成一个有序序列，比如将
[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]：
代码实现
寻找两个正序数组的中位数
题目：给定两个大小分别为
m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。示例：
数组中的逆序对
题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例：
合并阶段本质上是合并两个排序数组的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素至末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。