算法概述/思路
歸并排序是基于一種被稱為“分治”（divide and conquer）的策略。其基本思路是這樣的：
1.對于兩個有序的數組，要將其合并為一個有序數組，我們可以很容易地寫出如下代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//both a and b is ascend.public void merge(int[] a, int[] b, int[] c){ int i=0,j=0,k=0; while (i<=a.length && j<=b.length){ if (a[i]<=b[i]){ c[k++]=a[i++]; } else{ c[k++]=b[j++]; } } while (i<=a.length){ c[k++]=a[i++]; } while (j<=b.length){ c[k++]=b[j++]; }} |
容易看出，這樣的合并算法是高效的，其時間復雜度可達到O(n)。
2.假如有一個無序數組需要排序，但它的兩個完全劃分的子數組A和B分別有序，借助上述代碼，我們也可以很容易實現；
3.那么，如果A,B無序，怎么辦呢？可以把它們再分成更小的數組。
4.如此一直劃分到最小，每個子數組都只有一個元素，則可以視為有序數組。
5.從這些最小的數組開始，逆著上面的步驟合并回去，整個數組就排好了。
總而言之，歸并排序就是使用遞歸，先分解數組為子數組，再合并數組。
例子
下面舉例說明，假如要對數組a={2,1,3,5,2,3}進行排序，那么把數組劃分為{2,1,3}和{5,2,3}兩個子數組，這兩個子數組排序后變為{1,2,3}和{2,3,5}，然后對這兩個數組進行歸并操作便得到最終的有序數組。代碼實現如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
void sort(int[] a) { int[] aux = new int[a.length]; //輔助數組 mergeSort(a, 0, a.length - 1, aux);}void mergeSort(int[] a, int lo, int hi, int[] aux) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; mergeSort(a, lo, mid, aux); mergeSort(a, mid + 1, hi, aux); merge(a, lo, mid, hi, aux);}void merge(int[] a, int lo, int mid, int hi, int[] aux) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (aux[i] <= aux[j]) a[k] = aux[i++]; else a[k] = aux[j++]; }} |
另一種實現：自底向上的歸并排序
在上面的實現中，相當于將一個大問題分割成小問題分別解決，然后用所有小問題的答案來解決整個大問題。將一個大的數組的排序劃分為小數組的排序是自頂向下的排序。還有一種實現是自底向上的排序，即先兩兩歸并，然后四四歸并......代碼實現如下：
|
1
2
3
4
5
6
7
8
9
10
|
void sort(int[] a) { int N = a.length; int[] aux = new int[N]; for (int sz = 1; sz < N; sz += sz) { for (int lo = 0; lo < N - sz; lo += sz + sz) { //在每輪歸并中，最后一次歸并的第二個子數組可能比第一個子數組要小 merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux); } }} |
