一、原理解析
歸并排序不像前面講過(guò)的幾個(gè)排序那樣直觀卸亮，為了便于理解忽妒，我們先做個(gè)問(wèn)題分解。
假設(shè)有兩個(gè)已經(jīng)排序好的數(shù)組：
let arrLeft = [1, 3, 4, 7]
let arrRight = [2, 5, 6, 9]
如何把這兩個(gè)已排序好的數(shù)組合并成一個(gè)排序好的數(shù)組呢？
可以新建一個(gè)空數(shù)組arrResult锰扶，比較arrLeft 第一位和 arrRight 第一位献酗，哪個(gè)小就把這個(gè)數(shù)組的第一位拿出來(lái)push到空數(shù)組里。然后反復(fù)執(zhí)行上面的邏輯坷牛，直到arrLeft或者arrRight其中一個(gè)變?yōu)榭諗?shù)組罕偎。最后再把另一個(gè)不為空的全部拿出來(lái) push 到arrResult。 以下是代碼：
function merge(leftArr, rightArr) {
var resultArr = []
while(leftArr.length && rightArr.length) {
resultArr.push(leftArr[0] <= rightArr[0] ? leftArr.shift() : rightArr.shift())
}
return resultArr.concat(leftArr).concat(rightArr)
}
那回頭看看我們要真實(shí)解決的問(wèn)題京闰，如何對(duì)一個(gè)未排序的數(shù)組進(jìn)行排序呢颜及？
對(duì)于如下數(shù)組：
let arr = [4, 1, 2, 6, 9, 7, 3, 5]
我們可以把數(shù)組分成兩部分：
let part1 = [4, 1, 2, 6]
let part2 = [9, 7, 3, 5]
假設(shè)我們已經(jīng)寫(xiě)好了我們最終要實(shí)現(xiàn)的排序方法 mergeSort。那么 mergeSort(arr) 等價(jià)于merge(mergeSort(part1), mergeSort(part2)) 蹂楣。 即：對(duì)數(shù)組 arr 的排序俏站，等價(jià)于把數(shù)組分兩部分分別對(duì)每部分排序得到兩個(gè)排序的數(shù)組，然后再利用剛剛寫(xiě)好的merge 方法把兩個(gè)已經(jīng)排序好的數(shù)組合并成一個(gè)最終排序好的數(shù)組痊土。
那mergeSort(part1) 的結(jié)果又怎么計(jì)算呢肄扎？繼續(xù)遵循上面的邏輯，對(duì) part1繼續(xù)分解赁酝，直到分解為對(duì)長(zhǎng)度為1的數(shù)組進(jìn)行排序（直接返回即可）犯祠。
function mergeSort() {
//待補(bǔ)充
}
mergeSort(arr)
//等價(jià)于
merge(mergeSort(part1), mergeSort(part2))
總結(jié)：要排序一個(gè)大數(shù)組，可以把這個(gè)大數(shù)組拆分成兩個(gè)小數(shù)組酌呆，把問(wèn)題轉(zhuǎn)變成分別排序這兩個(gè)小數(shù)組衡载，再把排序后的兩個(gè)小數(shù)組通過(guò)簡(jiǎn)單的處理方式“歸并為”最終需要的結(jié)果。 如何排序這兩個(gè)小數(shù)組呢隙袁？循環(huán)剛剛的邏輯痰娱，直到數(shù)組拆分到極小（數(shù)組長(zhǎng)度為1菩收，排序的結(jié)果就是自己）梨睁。
二、代碼實(shí)現(xiàn)
以下是 JavaScript 版本的的代碼實(shí)現(xiàn)：
function mergeSort(arr) {
var merge = function(leftArr, rightArr) {
var resultArr = []
while(leftArr.length && rightArr.length) {
resultArr.push(leftArr[0] <= rightArr[0] ? leftArr.shift() : rightArr.shift())
}
return resultArr.concat(leftArr).concat(rightArr)
}
if(arr.length < 2) return arr
let mid = arr.length >> 1 //取數(shù)組的中位下標(biāo)娜饵，也可以用 parseInt(arr.length/2)
return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}
三而姐、復(fù)雜度
平均時(shí)間復(fù)雜度為 O(nlogn)，性能極好划咐。
