一，歸並排序介紹
歸並排序是一個典型的基於分治的遞歸算法。它不斷地將原數組分成大小相等的兩個子數組(可能相差1)，最終當劃分的子數組大小為1時(下面代碼第17行left小於right不成立時) ，將劃分的有序子數組合並成一個更大的有序數組。為什麼是有序子數組？？？
歸並排序的遞歸公式：T(N) = 2T(N/2) + O(N)
從公式中可以看出：將規模為 N 的原問題分解成兩個規模 N/2 的兩個子問題；並且，合並這兩個子問題的代價是 O(N)---[後面的 +O(N) 表示合並的代價]
二，歸並排序算法分析
歸並排序算法有兩個基本的操作，一個是分，也就是把原數組劃分成兩個子數組的過程。另一個是治，它將兩個有序數組合並成一個更大的有序數組。
它將數組平均分成兩部分: center = (left + right)/2，當數組分得足夠小時---數組中只有一個元素時，只有一個元素的數組自然而然地就可以視為是有序的，此時就可以進行合並操作了。因此，上面講的合並兩個有序的子數組，是從 只有一個元素 的兩個子數組開始合並的。
合並後的元素個數：從 1-->2-->4-->8......
比如初始數組：[24,13,26,1,2,27,38,15]
①分成了兩個大小相等的子數組：[24,13,26,1] [2,27,38,15]
②再劃分成了四個大小相等的子數組：[24,13] [26,1] [2,27] [38,15]
③此時，left < right 還是成立，再分：[24] [13] [26] [1] [2] [27] [38] [15]
此時，有8個小數組，每個數組都可以視為有序的數組了！！！，每個數組中的left == right，從遞歸中返回(從19行--20行的代碼中返回)，故開始執行合並(第21行)：
merge([24],[13]) 得到 [13,24]
merge([26],[1]) 得到[1,26]
.....
.....
最終得到 有序數組。
三，歸並排序算法實現
public class MergeSort {
public static <T extends Comparable<? super T>> void mergeSort(T[] arr) {
T[] tmpArray = (T[]) new Comparable[arr.length];
mergeSort(arr, tmpArray, 0, arr.length - 1);
}
/**
*
* @param arr an array of Comparable items
* @param tmpArray an array to place the merge result
* @param left the left-most index of the array
* @param right right-most index of the array
*/
private static <T extends Comparable<? super T>> void mergeSort(T[] arr,
T[] tmpArray, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(arr, tmpArray, left, center);
mergeSort(arr, tmpArray, center + 1, right);
merge(arr, tmpArray, left, center + 1, right);
}
}
/**
*
* @param arr an array of Comparable items
* @param tmpArray an array to place the merge result
* @param leftPos the left-most index of the subarray
* @param rightPos the index of the start of the second half
* @param rightEnd the right-most index of the subarray
*/
private static <T extends Comparable<? super T>> void merge(T[] arr,
T[] tmpArray, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int numElements = rightEnd - leftPos + 1;
int tmpPos = leftPos;// 只使用tmpArray中某一部分區域
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (arr[leftPos].compareTo(arr[rightPos]) <= 0)
tmpArray[tmpPos++] = arr[leftPos++];
else
tmpArray[tmpPos++] = arr[rightPos++];
}
while (leftPos <= leftEnd)
tmpArray[tmpPos++] = arr[leftPos++];// copy rest of left half
while (rightPos <= rightEnd)
tmpArray[tmpPos++] = arr[rightPos++];// copy rest of right half
// copy tmpArray back
for (int i = 0; i < numElements; i++, rightEnd--)
arr[rightEnd] = tmpArray[rightEnd];//只拷貝當前 merge 的部分數組
/**
* 復制了整個數組中的所有元素
for(int i = 0; i < tmpArray.length; i++)
arr[i] = tmpArray[i];
*/
}
//for test purpose
public static void main(String[] args) {
Integer[] arr = {24,13,26,1,2,27,38,15};
mergeSort(arr);
for (Integer i : arr)
System.out.print(i + " ");
}
}
①第3行的公共方法，是對外的排序接口，首先創建一個臨時數組tmpArray，用來保存合並過程中，兩個子數組臨時合並的結果。將tmpArray作為參數傳遞給遞歸調用的方法，而不是在執行遞歸調用的方法裡面創建臨時數組，這樣可以大大地減少臨時數組的創建。若在遞歸調用的方法裡創建臨時數組，每一層遞歸調用，都會創建一個臨時數組。
②第15行的私有方法，是執行遞歸調用的方法。在某次具體的遞歸調用中，只用到了tmpArray中的某一部分空間(leftEnd 和 rightEnd之間的空間)。
③第38行while循環，比較兩個子數組中的元素，誰小就把誰放到tmpArray中。
④第45行和第47行的兩個while循環完成的功能是：當合並兩個有序的子數組時，一個子數組中的元素已經全部放到tmpArray中去了，另一個子數組中還剩下有元素，故將剩下的所有元素直接復制到tmpArray中。
⑤第51行for循環，將本次merge完成的兩個子數組復制到原數組中去。注意，它只復制本次參與合並的兩個子數組中的元素。為什麼要復制到原數組中去呢？因為在下一次的合並過程中，需要合並的是更大的子數組，這個更大的數組，就是由上次合並的生成的有序小數組組成的。比如：
在合並這兩個數組時：[24] [13]
下一次合並的則是：[13,24] [1,26]
四，歸並排序算法復雜度分析
歸並排序中，用到了一個臨時數組，故空間復雜度為O(N)
由歸並排序的遞歸公式：T(N) = 2T(N/2) + O(N) 可知時間復雜度為O(NlogN)
數組的初始順序會影響到排序過程中的比較次數，但是總的而言，對復雜度沒有影響。平均情況 or 最壞情況下 它的復雜度都是O(NlogN)
此外，歸並排序中的比較次數是所有排序中最少的。原因是，它一開始是不斷地劃分，比較只發生在合並各個有序的子數組時。
因此，JAVA的泛型排序類庫中實現的就是歸並排序。因為：對於JAVA而言，比較兩個對象的操作代價是很大的，而移動兩個對象，其實質移動的是引用，代價比較小。（排序本質上是兩種操作：比較操作和移動操作）