一.歸并排序的思路
①把 n 個(gè)記錄看成 n 個(gè)長度為 l 的有序子表；
②進(jìn)行兩兩歸并使記錄關(guān)鍵字有序，得到 n/2 個(gè)長度為 2 的有序子表；
③重復(fù)第②步直到所有記錄歸并成一個(gè)長度為 n 的有序表為止。
二.歸并排序算法實(shí)例
對(duì)于歸并排序算法這類的分治算法，其核心就是"分解"和"遞歸求解"。對(duì)于"分解"實(shí)例，會(huì)在下面分析msort()方法中給出。我們先看合并的過程。
以下面描述的序列為例，在索引范圍內(nèi)[first , last)的序列還有九個(gè)整數(shù)元素，它由索引范圍為[first , mid]的四個(gè)元素有序子列表A和索引范圍[mid , last]的五個(gè)元素有序子列表B組成。
步驟1：比較arr[indexA]=7與arr[indexB]=12。將較小的元素7復(fù)制到數(shù)組tempArr的索引indexC處。并將indexA和indexC都指向下一個(gè)位置。
步驟2：比較arr[indexA]=10與arr[indexB]=12。將較小的元素10復(fù)制到數(shù)組tempArr的索引indexC處。并將indexA和indexC都指向下一個(gè)位置。
步驟3：比較arr[indexA]=19與arr[indexB]=12。將較小的元素12復(fù)制到數(shù)組tempArr的索引indexC處。并將indexB和indexC都指向下一個(gè)位置。
步驟4-7：依次成對(duì)比較兩子表的元素將17，19，21，25復(fù)制到數(shù)組tempArr。此時(shí)，indexA到達(dá)子表A的未尾(indexA = mid)，indexB引用的值為30。
步驟8-9：將未到尾部的子表剩余數(shù)據(jù)復(fù)制到tempArr中。
步驟10：將tempArr復(fù)制到原始數(shù)據(jù)arr中。
三.歸并排序算法的實(shí)現(xiàn)
了解了合并過程，那么理解下面的代碼并不是一件難事。下面提供了歸并算法的非泛型版本和泛型版本。
public class MergeSort 
{
public static void sort(Object[] arr) {
//create a temporary array to store partitioned elements
Object[] tempArr = arr.clone();
//call msort with arrays arr and tempArr along
//with the index range
msort(arr, tempArr, 0, arr.length);
}
public static <T extends Comparable<? super T>> void sort(T[] arr) {
//create a temporary aray to store partitioned elements
T[] tempArr = (T[]) arr.clone();
//call msort with arrays arr and tempArr along
//with the index range
msort(arr, tempArr, 0, arr.length);
}
private static void msort(Object[] arr, Object[] tempArr, int first,
int last) {
//if the sublist has more than 1 element continue
if (first + 1 < last) {
//for sublists of size 2 or more, call msort()
//for the left and right sublists and than
//merge the sorted sublists using merge()
int midpt = (last + first) / 2;
msort(arr, tempArr, first, midpt);
msort(arr, tempArr, midpt, last);
//if list is already sorted, just copy src to
//dest; this is an optimization that results in faster
//sorts for nearly ordered lists
if (((Comparable) arr[midpt - 1]).compareTo(arr[midpt]) <= 0)
return;
//the elements in the ranges [first,mid] and
//[mid,last] are ordered;merge the ordered sublists
//into an ordered sequence in the range [first , last]
//using the temporary array
int indexA, indexB, indexC;
//set indexA to scan sublist A with rang [first , mid]
//and indexB to scan sublist B with rang [mid , last]
indexA = first;
indexB = midpt;
indexC = first;
//while both sublists are not exhausted, compare
//arr[indexA] and arr[indexB]; copy the smaller
//to tempArr
while (indexA < midpt && indexB < last) {
if (((Comparable) arr[indexA]).compareTo(arr[indexB]) < 0) {
tempArr[indexC] = arr[indexA]; //copyto tempArr
indexA++; //increment indexA
} else {
tempArr[indexC] = arr[indexB]; //copyto tempArr
indexB++; //increment indexB
}
indexC++; //increment indexC
}
//copy the tail of the sublist that is not exhausted
while (indexA < midpt) {
tempArr[indexC++] = arr[indexA++]; //copy to tempArr
} while (indexB < last) {
tempArr[indexC++] = arr[indexB++]; //copy to tempArr
}
//copy elements form temporary array to original array
for (int i = first; i < last; i++)
arr[i] = tempArr[i];
}
}
}
上述代碼中最核心的msort()方法是一遞歸算法。下圖說明了msort()方法中子列表的分割與合并。
四.歸并排序算法的效率
歸并排序的最壞情況與平均情況運(yùn)行時(shí)間都為O(nlog
2n)。假定數(shù)組具有n=2
k個(gè)元素。如下圖：
在層數(shù)0上對(duì)msort()方法的第一個(gè)調(diào)用會(huì)產(chǎn)生兩個(gè)遞歸調(diào)用，這兩個(gè)遞歸調(diào)用產(chǎn)生長度為n/2的兩個(gè)半部分列表，而merge()方法將上述兩個(gè)半部分列表組合的一個(gè)有序的n元素列表；在層數(shù)1上存在兩個(gè)msort()方法的調(diào)用，每個(gè)調(diào)用又會(huì)產(chǎn)生另外兩個(gè)對(duì)長度為n/4的列表的遞歸調(diào)用。每個(gè)合并會(huì)將兩個(gè)長度為n/4的子列表連接為一個(gè)長度為n/2的有序列表；在層數(shù)2上存在對(duì)merge()方法的4=2
2個(gè)調(diào)用，每個(gè)調(diào)用會(huì)創(chuàng)建一個(gè)長度為n/4的有序列表。通常，在層數(shù)i上存在對(duì)merge()方法的2
i個(gè)調(diào)用，每個(gè)調(diào)用會(huì)創(chuàng)建一個(gè)長度為n/2
i的有序子列表。
層數(shù)0：存在對(duì)merge()方法的1=2
0次調(diào)用。這個(gè)調(diào)用對(duì)n個(gè)元素排序。
層數(shù)1：存在對(duì)merge()方法的2=2
1次調(diào)用。這個(gè)調(diào)用對(duì)n/2個(gè)元素排序。
層數(shù)2：存在對(duì)merge()方法的4=2
2次調(diào)用。這個(gè)調(diào)用對(duì)n/4個(gè)元素排序。
......
層數(shù)i：存在對(duì)merge()方法的2
i次調(diào)用。這個(gè)調(diào)用對(duì)n/i個(gè)元素排序。
在樹中的每一層，合并涉及具有線性運(yùn)行時(shí)間的n/2
i個(gè)元素，這個(gè)線性運(yùn)行時(shí)間需要少于n/2
i次的比較。在層數(shù)i上組合的2
i個(gè)合并操作需要少于2
i*n/2
i=n次的比較。假定n=2
k,分割過程會(huì)在n/2
k=1的k層數(shù)上終止。那么所有層上完成的工作總量為:k*n = nlog
2n。因此msort()方法的最壞情況效率為O(nlog
2n)。