簡介
歸並排序以O(NlogN)最壞情形時間運行，而所使用的比較次數幾乎是最優的。
這個算法中基本的操作是合並兩個已排序的表。基本的合並算法是取兩個輸入數組A和B，一個輸出數組C，以及3個計數器Actr、Bctr、Cctr，它們初始置於對應數組的開始端。A[Actr]和B[Bctr]中的較小者被拷貝到C中的下一個位置，相關的計數器向前推進一步。當兩個輸入表有一個用完的時候，則將另一個表中剩余部分拷貝到C中。
合並兩個已排序的表的時間顯然是線性的，因為最多進行N-1次比較，其中N是元素的總數。
算法描述：如果N=1，那麼只有一個元素需要排序，否則，遞歸地前將半部分數據和後半部分數據各自歸並排序，得到得到排序後的兩部分數據，然後使用上面描述的合並算法再將這兩部分合並到一起。
分治（divide-and-conquer）策略：它將問題分（divide）成一些小的問題然後遞歸求解，而治（conquer）的階段則將分的階段解得的各答案修補在一起。
實現代碼如下：
/**
* Internal method that makes recursive calls
* @param a an array of Comparable items
* @param tmpArray an array to place the merged result
* @param left the left-most index of the subarray
* @param right the right-most index of the subarray
*/
private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a,AnyType[] tmpArray,int left,int right) {
if(left<right){
int center = (left+right)/2;
mergeSort(a,tmpArray,left,center);
mergeSort(a,tmpArray,center+1,right);
merge(a,tmpArray,left,center+1,right);
}
}
/**
* Mergesort algorithm
* @param a an array of Comparable items
*/
public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a){
AnyType[] tmpArray = (AnyType[])new Comparable[a.length];
mergeSort(a,tmpArray,0,a.length-1);
}
/**
* Internal method that merges two sorted halves of a subarray
* @param a an array of Comparable items
* @param tmpArray an array to place the merged 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 <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] a,AnyType[] tmpArray,int leftPos,int rightPos,int rightEnd){
int leftEnd = rightPos -1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
//main loop
while(leftPos<=leftEnd && rightPos<=rightEnd){
if(a[leftPos].compareTo(a[rightPos])<=0){
tmpArray[tmpPos++] = a[leftPos++];
}else{
tmpArray[tmpPos++] = a[rightPos++];
}
}
//Copy rest of the first array
while(leftPos<=leftEnd){
tmpArray[tmpPos++] = a[leftPos++];
}
//Copy rest of the right array
while(rightPos<=rightEnd){
tmpArray[tmpPos++] = a[rightPos++];
}
//Copy tmpArray back
for(int i=0;i<numElements;i++,rightEnd--){
a[rightEnd] = tmpArray[rightEnd];
}
}
歸並排序分析
與其它的O(NlogN)排序算法比較，歸並排序的運行時間嚴重依賴於比較元素和在數組（以及臨時數組）中移動元素的相對開銷。這些開銷是和語言相關的。
在Java中，當執行一次泛型排序（使用Comparator）時，進行一次元素比較可能是昂貴的（因為比較可能不容易被內嵌，從而動態調度的開銷可能會減慢執行的速度），但是移動元素則是省時的（因為它們是引用的賦值，而不是龐大對象的拷貝）。它就是標准Java類庫中泛型排序所使用的算法。在Java中，快速排序用作基本類型的標准庫排序。
在C++的泛型排序中，如果對象龐大，那麼拷貝對象可能需要很大開銷，而由於編譯器具有主動執行內嵌優化的能力，因此比較對象常常是相對省時的。C++類庫中通常使用快速排序（Quicksort）。
