歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。值得注意的是歸并排序是一種穩定的排序方法。速度僅次于快速排序，為穩定排序算法，一般用于總體無序，但是各子項相對有序的數列。若將兩個有序表合并成一個有序表，稱為二路[歸并](http://baike.baidu.com/view/711818.htm)。
**1、算法思想**
比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]復制到r[k]中，并令i和k分別加上1；否則將第二個有序表中的元素a[j]復制到r[k]中，并令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然后再將另一個有序表中剩余的元素復制到r中從下標k到下標t的單元。
歸并排序的算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最后把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。
基本思路就是將數組分成二組A，B，如果這二組組內的數據都是有序的，那么就可以很方便的將這二組數據進行排序。如何讓這二組組內數據有序了？可以將A，B組各自再分成二組。依次類推，當分出來的小組只有一個數據時，可以認為這個小組組內已經達到了有序，然后再合并相鄰的二個小組就可以了。這樣通過先遞歸的分解數列，再合并數列就完成了歸并排序。
（1）分治法的三個步驟
設歸并排序的當前區間是R[low..high]，分治法的三個步驟是：
①分解：將當前區間一分為二，即求分裂點? ? ? ? ?
②求解：遞歸地對兩個子區間R[low..mid]和R[mid+1..high]進行歸并排序；
③組合：將已排序的兩個子區間R[low..mid]和R[mid+1..high]歸并為一個有序的區間R[low..high]。
遞歸的終結條件：子區間長度為1（一個記錄自然有序）。
**2、代碼實現：**
~~~
package sort;
public class MergingSort {
public static void main(String[] args) {
int[] a = {3, 2, 5, 4, 1};
sort(a, 0, a.length - 1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
public static void sort(int[] data, int left, int right) {
if (left < right) {
// 首先找出中間的索引
int center = (left + right) / 2;
// 對左邊的數組進行遞歸,使左邊有序
sort(data, left, center);
// 對中間索引右邊的數組進行遞歸，使右邊有序
sort(data, center + 1, right);
// 再將二個有序數列合并
merge(data, left, center, right);
}
}
public static void merge(int[] data, int left, int center, int right) {
int[] tmpArr = new int[data.length];
int mid = center + 1;
// third記錄中間數組的索引
int third = left;
int tmp = left;
while (left <= center && mid <= right) {
// 將兩個數組中取出最小的數放入中間數組
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入中間數組
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
}
~~~
**3、算法分析**
1、穩定性
歸并排序是一種穩定的排序。
2、存儲結構要求
可用順序存儲結構。也易于在鏈表上實現。
3、時間復雜度
對長度為n的文件，需進行
**lgn**
**趟二路歸并，每趟歸并的時間為O(n)，故其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。**
4、空間復雜度
需要一個輔助向量來暫存兩有序子文件歸并的結果，故其輔助空間復雜度為O(n)，顯然它不是就地排序。
注意：
若用單鏈表做存儲結構，很容易給出就地的歸并排序。
5、比較操作的次數介于(nlogn) / 2和nlogn - n + 1。
6、賦值操作的次數是(2nlogn)。歸并算法的空間復雜度為：0 (n)
7、歸并排序比較占用內存，但卻是一種效率高且穩定的算法。
代碼地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/MergingSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/MergingSort.java)
