歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應用凿试。將已有序的子序列合并排宰，得到完全有序的序列；即先使每個子序列有序那婉，再使子序列段間有序板甘。若將兩個有序表合并成一個有序表，稱為二路歸并详炬。歸并排序是一種穩(wěn)定的排序方法盐类。
歸并排序的時間復雜度為O(N log N)，空間復雜度為T(N)
實現(xiàn)歸并的一種直截了當?shù)霓k法是將兩個不同的有序數(shù)組歸并到第三個數(shù)組中呛谜，兩個數(shù)組中的元素都應該實現(xiàn)了 Comparable 接口在跳，實現(xiàn)的方法很簡單，創(chuàng)建一個適當大小的數(shù)組然后將兩個輸入數(shù)組的元素一個個從小到大放入這個數(shù)組中呻率。
但是硬毕，用歸并將一個大數(shù)組排序時，則需要進行很多次歸并礼仗，如果每次歸并都創(chuàng)建一個數(shù)組來存儲排序結果吐咳，會帶來問題逻悠，因為下面實現(xiàn)了一種能夠在原地歸并的、自頂向下的歸并排序算法韭脊。偽代碼如下：
public class MergeSort {
// 歸并所需的輔助數(shù)組
private static Comparable[] aux;
public static void Sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
/**
* 將數(shù)組a[lo...hi]排序
*
* @param a
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) {
return;
}
int mid = lo + (hi - lo) / 2;
// 左半部分排序
sort(a, lo, mid);
// 右半部分排序
sort(a, mid + 1, hi);
// 歸并結果
merge(a, lo, mid, hi);
}
/**
* 原地歸并（避免將兩個不同的有序數(shù)組歸并到第三個數(shù)組中）的抽象方法
*
* @param a
* @param lo
* @param mid
* @param right
*/
public static void merge(Comparable[] a, int lo, int mid, int hi) {
// 將a[lo...mid]和a[mid+1...hi]歸并
int i = lo;
int j = mid + 1;
Comparable[] aux = new Comparable[a.length];
for (int k = 0; k <= hi; k++) {
// 將a[lo...hi]復制到aux[lo...hi]
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].compareTo(aux[j])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
}
