開篇
上篇聊到的堆排序僅用線性對數(shù)級別的時(shí)間復(fù)雜度 O(n log n) 和常數(shù)級別的額外輔助空間即可將一個(gè)數(shù)組排序泰佳，已然十分高效阳柔。這篇我們來聊一種同樣高效但要更古老的排序算法——?dú)w并排序。
正文
何為歸并排序
此算法于 1945 年由計(jì)算機(jī)科學(xué)的祖師爺——約翰·馮·諾伊曼（對就是那個(gè)大名鼎鼎的馮·諾依曼）首次提出樟蠕，看年代確實(shí)挺古老的柒凉！
將兩個(gè)已經(jīng)（整體）有序的數(shù)組合并成一個(gè)更大的有序數(shù)組稠腊，這就叫歸并：
原始數(shù)組：[6, 5, 3, 1, 8, 7, 2, 4]
---------------------|
---------------------|
左半排序：[1, 3, 5, 6]|------------
右半排序：------------|[2, 4, 7, 8]
歸并操作：[1, 2, 3, 4, 5, 6, 7, 8]
自頂向下的遞歸實(shí)現(xiàn)
歸并排序是算法里面分治法的典型應(yīng)用，一種經(jīng)典的實(shí)現(xiàn)是采用遞歸的方法自頂向下分而治之是
來張動(dòng)圖具象化展示下以幫助理解畸陡，圖源維基百科：
具體邏輯如此，下面我們直接上代碼（Java）來看看歸并排序到底是怎么一回事丁恭，實(shí)現(xiàn)中有個(gè)將兩個(gè)有序數(shù)組歸并成一個(gè)有序數(shù)組的操作我們將其抽象成一個(gè)單獨(dú)的工具方法曹动，命名為 merge（其實(shí)是將當(dāng)前數(shù)組兩個(gè)有序的子數(shù)組歸并）。一點(diǎn)注意牲览，此方法需要額外的輔助空間：
/**
* @param array:待歸并數(shù)組墓陈，我們需要將此數(shù)組的[start, mid] 和 [mid + 1, end] 兩個(gè)已經(jīng)有序的子數(shù)組歸并起來
* @param aux:輔助數(shù)組，完成歸并操作的額外輔助空間第献，其大小應(yīng)和 array 一致
* @param start:歸并區(qū)間起始位置贡必，inclusive
* @param mid:歸并區(qū)間第一個(gè)子數(shù)組的有邊界，inclusive
* @param end:歸并區(qū)間終止位置痊硕，inclusive
*/
private static void merge(int[] array, int[] aux, int start, int mid, int end){
//將 array 的 [start, mid] 和 [mid + 1, end] 兩個(gè)已有序的子數(shù)組歸并
int s1 = start;//start1
int s2 = mid + 1;//start2
for (int i = start; i <= end; i++){//拷貝待排序數(shù)組
aux[i] = array[i];
}
//開始?xì)w并兩個(gè)(子)數(shù)組
for (int i = start; i <= end; i++){
if (s1 > mid){ //第一個(gè)子數(shù)組(左半邊)已遍歷完
array[i] = aux[s2++];
}else if (s2 > end){ //第二個(gè)子數(shù)組(右半邊)已遍歷完
array[i] = aux[s1++];
}else if (aux[s1] > aux[s2]){//平凡情況赊级，取右半邊元素
array[i] = aux[s2++];
}else { //平凡情況，取左半邊元素
array[i] = aux[s1++];
}
}
}
/**
* <p>歸并排序自頂向下的遞歸實(shí)現(xiàn)</p>
* @param array:待排序數(shù)組岔绸，將數(shù)組的 [start, end] 區(qū)間排序
* @param aux:輔助數(shù)組理逊，完成歸并操作的額外輔助空間橡伞，其大小應(yīng)和 array 一致
* @param start:待排序區(qū)間起始位置，inclusive
* @param end:待排序區(qū)間終止位置晋被，inclusive
*/
public static void sortMerge(int[] array, int[] aux, int start, int end){
if(end <= start){//遞歸結(jié)束條件
return;
}
int mid = start + (end - start)/2;//歸并左半部分的終止位置兑徘，右半部分的起始位置自然是 mid + 1
sortMerge(array, aux, start, mid);//左半部分排序
sortMerge(array, aux, mid + 1, end);//右半部分排序
merge(array, aux, start, mid, end);//歸并兩個(gè)已排序的子數(shù)組
}
其中 sortMerge 方法的遞歸邏輯可能不是那么容易理解，需要好好消化一下羡洛。以數(shù)組 [6, 5, 3, 1, 8, 7, 2, 4] 為例挂脑，我們一起來捋下其排序遞歸操作的函數(shù)調(diào)用軌跡來幫助理解：
-------------a = [6, 5, 3, 1, 8, 7, 2, 4]
-------------sortMerge(a, aux, 0, 7)//為此數(shù)組初始調(diào)用歸并排序，設(shè)輔助數(shù)組為 aux
-------------
左半部分排序：sortMerge(array, aux, 0, 3)----------------------->瞧見沒欲侮，典型的分而治之
------------- sortMerge(array, aux, 0, 1)
------------- merge(array, aux, 0, 0, 1)
------------- sortMerge(array, aux, 2, 3)
------------- merge(array, aux, 2, 2, 3)
右半部分排序：sortMerge(array, aux, 4, 7)----------------------->瞧見沒崭闲，典型的分而治之
------------- sortMerge(array, aux, 4, 5)
------------- merge(array, aux, 4, 4, 5)
------------- sortMerge(array, aux, 6, 7)
------------- merge(array, aux, 6, 6, 7)
歸并結(jié)果----：merge(array, aux, 0, 3, 7)
為避免遞歸帶來的額外開銷，還請讀者自行把上面的代碼改造成非遞歸版本威蕉。
上面提到了自頂向下這種說法刁俭，仔細(xì)觀察算法的執(zhí)行過程，我們是將一個(gè)大問題分割成（兩個(gè)）小問題來分別解決韧涨，然后用所有小問題的解來得到整個(gè)大問題的解（典型的分而治之）牍戚。其實(shí)反之亦是一種不錯(cuò)的實(shí)現(xiàn)思路，也即自底向上：首先我們進(jìn)行兩兩歸并（把數(shù)組每個(gè)元素看成一個(gè)大小為 1 的子數(shù)組虑粥，將相鄰兩個(gè)子數(shù)組歸并到一起如孝，每次歸并兩個(gè)元素）然后四四歸并、八八歸并（粒度越來越粗）娩贷，直至數(shù)組整體有序第晰。
自底向上的嵌套循環(huán)實(shí)現(xiàn)
/**
*<p>歸并排序自底向上的嵌套循環(huán)實(shí)現(xiàn)</p>
* @param array:待排序數(shù)組，將數(shù)組的 [start, end] 區(qū)間排序
* @param aux:輔助數(shù)組育勺，完成歸并操作的額外輔助空間但荤，其大小應(yīng)和 array 一致
*/
public static void sortMerge_(int[] array, int[] aux){
for (int size = 1; size < array.length; size <<= 1){//子數(shù)組的大小每次都翻倍
//根據(jù)當(dāng)前每個(gè)子數(shù)組的大小 size，按順序?qū)ο噜弮蓚€(gè)子數(shù)組應(yīng)用歸并操作涧至，注意每個(gè)子數(shù)組在當(dāng)前 size 下只參與一次歸并操作
for (int start = 0; start < array.length - size; start += size + size){
int end = start + size + size - 1;
//這里的 merge 方法跟上面的自頂向下的一致
merge(array, aux, start, start + size - 1, Math.min(end, array.length - 1));//最后一次歸并時(shí)腹躁，第二個(gè)子數(shù)組可能比第一個(gè)體積要小，或者跟第一個(gè)相等南蓬，我們的歸并操作支持為兩個(gè)大小不同的數(shù)組應(yīng)用
}
}
}
上面的代碼跟我們一開始實(shí)現(xiàn)的自頂向下版本是基本等價(jià)的纺非，可以看到其代碼要精簡許多。還是以數(shù)組 [6, 5, 3, 1, 8, 7, 2, 4] 為例赘方，其方法執(zhí)行軌跡如下：
-------------自底向上對數(shù)組歸并排序
-------------a = [6, 5, 3, 1, 8, 7, 2, 4]
-------------sortMerge(a, aux)//自底向上歸并排序烧颖，設(shè)輔助數(shù)組為 aux
-------------
------------- size = 1
------------- merge(array, aux, 0, 0, 1)
------------- merge(array, aux, 2, 2, 3)
------------- merge(array, aux, 4, 4, 5)
------------- merge(array, aux, 6, 6, 7)
------------- size = 2
------------- merge(array, aux, 0, 1, 3)
------------- merge(array, aux, 4, 5, 7)
-------------size = 4
-------------merge(array, aux, 0, 3, 7)
-------------數(shù)組已整體有序
*/
總結(jié)
如上所述，歸并排序是建立在歸并操作基礎(chǔ)上的一種高效窄陡、穩(wěn)定的排序算法炕淮，其時(shí)間復(fù)雜度恒為線性對數(shù)級別的 O(n log n) ，與輸入無關(guān)跳夭。與我們之前討論的排序算法不同涂圆，其實(shí)現(xiàn)需要額外的輔助空間们镜，空間復(fù)雜度最壞為線性級別的 O(n)。
尾巴
因其高效性润歉，歸并排序是當(dāng)下應(yīng)用非常廣泛的排序算法模狭，很多語言的的標(biāo)準(zhǔn)函數(shù)庫中涉及到排序的地方一般都有其實(shí)現(xiàn)（比如Java）。那歸并排序是應(yīng)用最廣泛的排序算法嗎踩衩？答案是否定的嚼鹉，下篇我們就來聊一種更加高效，且是目前應(yīng)用最廣泛的排序算法——快速排序（你看這名字Ｇ弧）锚赤。
