目標：將一個數(shù)組按照由低到高（或者由高到低）的順序排序。
歸并排序算法由 馮諾依曼 1945年發(fā)明巍膘。它是一種高效的排序算法厂财，其最好、平均峡懈、最差時間復(fù)雜度都是O(n log n)璃饱。
歸并排序算法使用了分治法（divide and conquer），即將一個大的問題分成更小的問題并解決它們肪康。我認為歸并算法就是拆分再合并荚恶。
假設(shè)你需要將一個大小為 n 的數(shù)組排序。歸并排序算法的排序步驟是：
- 將所有的數(shù)字放入一個無序的堆磷支。
- 將堆分成兩部分谒撼，現(xiàn)在你有兩個無序的堆。
- 持續(xù)將無序的堆拆分雾狈，直到無法再拆分為止廓潜，你將得到 n 個堆，每一個堆中有一個數(shù)字。
- 現(xiàn)在開始將這些堆按照一定順序按對合并辩蛋。每一次合并過程中呻畸，將堆中的數(shù)字放入有序的隊列。這一點很容易實現(xiàn)堪澎，因為每一個獨立的堆中的內(nèi)容都是有序的擂错。
示例
拆分
假設(shè)你有一個數(shù)組 [2, 1, 5, 4, 9]。這是一個無序的堆樱蛤。拆分的目的就是一直拆分，直到不可再拆分為止剑鞍。
首先昨凡，將數(shù)組分成兩堆： [2, 1] 和 [5, 4, 9]。還能繼續(xù)拆嗎蚁署？可以便脊！
先看左邊的堆[2, 1]分成 [2] 和 [1]，還能繼續(xù)拆嗎光戈？不能哪痰，現(xiàn)在來看另一個堆。
將 [5, 4, 9] 分成 [5] 和 [4, 9]久妆， 毫無疑問[5] 已經(jīng)不能再分晌杰，但是 [4, 9]可以分成 [4] 和 [9]。
拆分的過程結(jié)束時筷弦，有這樣一些堆：[2] [1] [5] [4] [9] 肋演。注意每一個堆中都只有一個數(shù)字。
合并
現(xiàn)在有了一堆拆開的數(shù)組烂琴，你需要在合并它們的同時對它們進行排序爹殊。記住，合并是逐漸地將很多小數(shù)組合并奸绷，而不是一次合并出一個大的數(shù)組梗夸。在每一次合并迭代中，你需要關(guān)注的是將一個堆與另一個堆合并号醉。
現(xiàn)在這些堆就是 [2] [1] [5] [4] [9]反症，第一次合并的結(jié)果是 [1, 2] ，[4, 5] 和 [9]扣癣。由于[9] 落單了惰帽，在這一輪合并中它無法與其他堆合并。
下一輪是合并 [1, 2] 和 [4, 5]父虑，結(jié)果是[1, 2, 4, 5]该酗， [9] 繼續(xù)落單。
現(xiàn)在只有兩個堆[1, 2, 4, 5] 和 [9]，現(xiàn)在是時候?qū)⑺鼈兒喜⒘宋仄牵Y(jié)果就是一個有序的數(shù)組 [1, 2, 4, 5, 9]悔叽。
遞歸法（Top-down）
我們先來看一個 Kotlin 實現(xiàn)的歸并排序：
fun mergeSort(array: IntArray): IntArray {
if (array.size < 2) {
return array //1
}
val middleIndex = array.size / 2 //2
val leftArray = mergeSort(array.sliceArray(0 until middleIndex)) //3
val rightArray = mergeSort(array.sliceArray(middleIndex until array.size))//4
return merge(leftArray, rightArray) //5
}
我們逐行解讀這個函數(shù)：
- 如果數(shù)組是空的或者只有一個元素，就沒有必要繼續(xù)拆分爵嗅，直接返回即可娇澎。
- 找到數(shù)組的中間位置。
- 根據(jù)上一步找到的中間位置，遞歸拆分數(shù)組的左半部分砸抛。
- 同樣遞歸拆分數(shù)組的右半部分窿克。
- 最后，將所有的值合并到一起戚啥，保證合并后的結(jié)果是有序的。
再來看一下合并算法：
private fun merge(leftPile: IntArray, rightPile: IntArray): IntArray {
//1
var leftIndex = 0
var rightIndex = 0
//2
var orderedPile = intArrayOf()
//3
while (leftIndex < leftPile.size && rightIndex < rightPile.size) {
when {
leftPile[leftIndex] < rightPile[rightIndex] -> {
orderedPile += leftPile[leftIndex]
leftIndex++
}
leftPile[leftIndex] > rightPile[rightIndex] -> {
orderedPile += rightPile[rightIndex]
rightIndex++
}
else -> {
orderedPile += leftPile[leftIndex]
leftIndex++
orderedPile += rightPile[rightIndex]
rightIndex++
}
}
}
//4
while (leftIndex < leftPile.size) {
orderedPile += leftPile[leftIndex]
leftIndex++
}
while (rightIndex < rightPile.size) {
orderedPile += rightPile[rightIndex]
rightIndex++
}
return orderedPile
}
這個函數(shù)看起來可能很可怕锉试，但是它其實很簡單：
- 在合并的過程中需要兩個游標用于跟蹤兩個數(shù)組的合并過程猫十。
- 這個是存放合并結(jié)果的數(shù)組。一開始它是一個空的數(shù)組呆盖，但是你在隨后的步驟中會將其他數(shù)組中的元素添加進去拖云。
- 這個 while 循環(huán)就從左往右逐一比較兩個數(shù)組中的元素并將它們添加到
orderedPile，這樣就保證了結(jié)果是有序的应又。 - 當前面的 while 結(jié)束的時候宙项，意味著
leftPile或者rightPile已經(jīng)完全合并到了orderedPile。這個時候丁频，就不再需要比較杉允，直接將另一個數(shù)組中剩余的部分直接添加到orderedPile。
為了說明 merge() 函數(shù)的運行過程席里，我們假設(shè)現(xiàn)在有兩個堆：leftPile = [1, 7, 8] 以及 rightPile = [3, 6, 9]叔磷。注意每一個堆中的元素都已經(jīng)是有序的 -- 這一點在歸并排序中是肯定成立的。下面是將兩個堆合并的過程：
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ ]
l r
leftIndex（這我們用 l代表）指向 leftPile 的第一個元素 1奖磁。rightIndex（我們用 r 代表）指向 3改基。所以，添加到 orderedPile中的第一個元素時 1咖为，同時將 left index l 向右移動一個位置秕狰。
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1 ]
-->l r
現(xiàn)在 l 指向 7， 但是 r 還指向 3躁染，我們將最小的那一個元素加入有序堆鸣哀，所以應(yīng)該是 3。現(xiàn)在的情況是：
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3 ]
l -->r
重復(fù)以上步驟吞彤。每一步我們都從 leftPile 或者 rightPile中取一個最小值放入 orderedPile:
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6 ]
l -->r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7 ]
-->l r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7, 8 ]
-->l r
現(xiàn)在左側(cè)的堆中已經(jīng)沒有數(shù)據(jù)我衬。我們只需要將右側(cè)堆中剩余的項目添加到 orderedPile叹放。最終的結(jié)果是： [ 1, 3, 6, 7, 8, 9 ]。
注意這個算法非常簡單：它從左向右遍歷兩個堆挠羔，每一步都取一個最小的數(shù)字井仰。最終的結(jié)果能夠有序是因為我們保證了合并的每一個堆都已經(jīng)是有序的。
迭代法（Bottom-up）
上面我們所實現(xiàn)的歸并排序算法稱為遞歸法破加，因為他首先將數(shù)組拆分成更小的堆然后再合并俱恶。在排序數(shù)組的時候，實際上你可以跳過拆分的步驟立即執(zhí)行數(shù)組元素的合并范舀。這就是所謂的迭代法合是。
是時候加強一點難度了。先來看一個完整的迭代法實現(xiàn)：
fun <T> mergeSortBottomUp(array: Array<T>, isOrderedBofore: (T, T) -> Boolean): Array<T> {
val n = array.size
val z = arrayOf(array.clone(), array.clone()) //1
var d = 0
var width = 1
while (width < n) { //2
var i = 0
while (i < n) { //3
var j = i
var l = i
var r = i + width
val lmax = minOf(l + width, n)
val rmax = minOf(r + width, n)
while (l < lmax && r < rmax) { //4
if (isOrderedBofore(z[d][l], z[d][r])) {
z[1 - d][j] = z[d][l]
l++
} else {
z[1 - d][j] = z[d][r]
r++
}
j++
}
while (l < lmax) {
z[1 - d][j] = z[d][l]
l++
j++
}
while (r < rmax) {
z[1 - d][j] = z[d][r]
r++
j++
}
i += width * 2
}
width *= 2
d = 1 - d //5
}
return z[d]
}
這個函數(shù)看起來比遞歸法版本要恐怖多了尿背，但是注意函數(shù)體中包含了和 merge() 方法一樣的 while 循環(huán)端仰。
我們先用一個實例來說明一下迭代排序的排序過程，假設(shè)有一個數(shù)組 [6, 2, 8, 1, 5, 4, 12, 3, 9] 需要排序田藐。一開始我們就申請了一個二維數(shù)組 z ，里面存放了兩份待排序的數(shù)組：
[[6, 2, 8, 1, 5, 4, 12, 3, 9],
[6, 2, 8, 1, 5, 4, 12, 3, 9]]
第一步從二維數(shù)組的第一個元素z[0] 中取出數(shù)字吱七，按照兩兩結(jié)對排序合并（也就是合并大小為1的堆汽久，對應(yīng) width = 1 ），并將結(jié)果存入z[1]:
[[6, 2, 8, 1, 5, 4, 12, 3, 9],
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
-- -- -- -- |
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[2, 6, 1, 8, 4, 5, 3, 12, 9]]
然后將合并的寬度加倍（width = 2）踊餐，從 z[1]中取出數(shù)字合并排序景醇，將結(jié)果存入 z[0]：
[[1, 2, 6, 8, 3, 4, 5, 12, 9],
↑ ↑ ↑ ↑ ↑
---------- --------- |
↑ ↑ ↑ ↑ ↑
[2, 6, 1, 8, 4, 5, 3, 12, 9]]
如此循環(huán)，每次都需要將寬度加倍吝岭，并且切換待排序數(shù)據(jù)的來源以及排序結(jié)果的存入位置三痰，對應(yīng)代碼中的 d = 1- d，從 z[d]中讀數(shù)據(jù)窜管，排序結(jié)果存入z[1-d]：
[[1, 2, 6, 8, 3, 4, 5, 12, 9],
↓ ↓ ↓
----------------------- |
↓ ↓ ↓
[1, 2, 3, 4, 5, 6, 8, 12, 9]]
[[1, 2, 3, 4, 5, 6, 8, 9, 12],
↑ ↑
--------------------------
↑ ↑
[1, 2, 3, 4, 5, 6, 8, 12, 9]]
最終得到排序好的數(shù)組z[d] : [1, 2, 3, 4, 5, 6, 8, 9, 12]散劫。
再來看一下代碼中的關(guān)鍵邏輯：
- 歸并排序算法需要一個臨時的數(shù)組作為工作區(qū)，因為你不能在合并左右堆的同時覆蓋它們的內(nèi)容幕帆。因為每次申請一個新的數(shù)組對資源是極大的浪費获搏，所以為我們使用了兩個數(shù)組，然后通過
d的值在兩個數(shù)組之間切換失乾，d的值只能是 0 或者 1.數(shù)組z[d]用于讀取數(shù)據(jù)常熙，z[1-d]用于寫入數(shù)據(jù)。這就是所謂的雙緩沖區(qū)碱茁。 - 從概念上講裸卫，迭代法版本和遞歸法版本的工作原理是一樣的。首先它將只有一個元素的堆合并纽竣，然后合并有兩個元素的堆墓贿，然后是有4個元素的堆，等等。堆的大小由
width決定募壕。一開始调炬，width是1，但是在每一次循環(huán)迭代結(jié)束時舱馅，我們將它的值乘以2缰泡，所以外層的循環(huán)決定了每次合并的堆的大小，并且每次循環(huán)之后待合并的子數(shù)組都會增大代嗤。 - 這個內(nèi)部循環(huán)逐一檢查堆中的每一個元素并將每一對堆合并成一個更大的堆棘钞。合并后的結(jié)果存入數(shù)組
z[1-d]。 - 這里的邏輯和遞歸版本是一樣的干毅。主要的區(qū)別是使用了雙緩沖區(qū)宜猜，所以數(shù)據(jù)從
z[d]中讀出來然后存入z[1-d]。同時使用了isOrderedBofore來比較元素硝逢，而不是單純的比較數(shù)字大小姨拥。所以這個歸并排序算法是一個通用算法，你可以用它來排序任何類型的對象渠鸽。 - 這個時候叫乌，從
z[d]中讀取出來的大小為width的堆已經(jīng)被合并成一個大小為width*2的大堆并存放在z[1-d]。在這里我們需要交換兩個數(shù)組徽缚，所以下一步我們就從剛剛創(chuàng)建的新堆中讀取數(shù)據(jù)憨奸。
這個函數(shù)是一個泛型函數(shù)，所以你可以用它來排序任何你需要的類型凿试，只有你提供合適的 isOrderedBofore函數(shù)來比較元素排宰。
使用范例：
val numList: Array<Int> = arrayOf(21, 3, 12, 45, 6, 9, 56, 67, 1, 43, 0)
val sortedNum = mergeSortBottomUp(numList) { x, y -> x < y }
val sortedNumUp = mergeSortBottomUp(numList) { x, y -> x > y }
val strList: Array<String> = arrayOf("e", "m", "ec", "q", "a", "dx", "adxz", "rf", "po")
val sortedStr = mergeSortBottomUp(strList) { x: String, y: String -> x < y }
val sortedStrUp = mergeSortBottomUp(strList) { x: String, y: String -> x > y }
性能
歸并排序算法的運行速度取決于待排序數(shù)組的大小。數(shù)組越大那婉，需要做的事情就越多板甘。
不管待排序的數(shù)組初始狀態(tài)是否有序，都不會影響歸并排序算法的運行速度吧恃，因為不管初始狀態(tài)是否有序虾啦，拆分的步驟都不會變。
所有痕寓，它的時間復(fù)雜度（最優(yōu)傲醉、平均、最差）都是O(n log n)呻率。
歸并排序算法的一個缺點就是需要一個臨時工作區(qū)硬毕，其大小與待排序數(shù)組的大小相同。它不是就地排序礼仗。
大多數(shù)歸并排序算法的實現(xiàn)都是穩(wěn)定排序吐咳。對于擁有相同排序鍵值的元素在排序后保持原來的相對位置不變逻悠。這一點對于一些簡單的數(shù)據(jù)如數(shù)字或者字符串顯得不是那么重要，但是對一些復(fù)雜的對象排序時非常重要韭脊。
本文編譯自： Switf 算法俱樂部 - 歸并排序
