歸并排序算法

（1）基本思想：歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。

（2）歸并排序：是建立在歸并操作上的一種有效，穩定的排序算法。

什么是歸并操作？

歸并操作，也叫歸并算法，指的是將兩個順序序列合并成一個順序序列的方法。
如　設有數列{6，202，100，301，38，8，1}
初始狀態：6,202,100,301,38,8,1
第一次歸并后：{6,202},{100,301},{8,38},{1}，比較次數：3；
第二次歸并后：{6,100,202,301}，{1,8,38}，比較次數：4；
第三次歸并后：{1,6,8,38,100,202,301},比較次數：4；
總的比較次數為：3+4+4=11；
逆序數為14；

示例代碼：

/*** 歸并排序* @param nums 待排序數組* @param l 開始索引：0* @param h 最大索引：nums.length - 1* @return 排序好的數組*/
public static int[] mergeSort(int[] nums, int l, int h) {if (l == h)return new int[]{nums[l]};int mid = l + (h - l) / 2;int[] leftArr = mergeSort(nums, l, mid); //左有序數組int[] rightArr = mergeSort(nums, mid + 1, h); //右有序數組int[] newNum = new int[leftArr.length + rightArr.length]; //新有序數組int m = 0, i = 0, j = 0;while (i < leftArr.length && j < rightArr.length) {newNum[m++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];}while (i < leftArr.length)newNum[m++] = leftArr[i++];while (j < rightArr.length)newNum[m++] = rightArr[j++];return newNum;
}