[[428236]]

本文轉(zhuǎn)載自微信公眾號(hào)「JS每日一題」，作者灰灰。轉(zhuǎn)載本文請(qǐng)聯(lián)系JS每日一題公眾號(hào)。

一、是什么

歸并排序(Merge Sort)是建立歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法的一個(gè)非常典型的應(yīng)用

將已有序的子序列合并，得到完全有序的序列，即先使每個(gè)子序列有序，再使子序列段間有序

例如對(duì)于含有 n 個(gè)記錄的無序表，首先默認(rèn)表中每個(gè)記錄各為一個(gè)有序表(只不過表的長(zhǎng)度都為 1)

然后進(jìn)行兩兩合并，使 n 個(gè)有序表變?yōu)閚/2 個(gè)長(zhǎng)度為 2 或者 1 的有序表(例如 4 個(gè)小有序表合并為 2 個(gè)大的有序表)

通過不斷地進(jìn)行兩兩合并，直到得到一個(gè)長(zhǎng)度為 n 的有序表為止

例如對(duì)無序表{49，38，65，97，76，13，27}進(jìn)行歸并排序分成了分、合兩部分：

如下圖所示：

歸并過程中，每次得到的新的子表本身有序，所以最終得到有序表

上述分成兩部分，則稱為二路歸并，如果分成三個(gè)部分則稱為三路歸并，以此類推

二、如何實(shí)現(xiàn)

關(guān)于歸并排序的算法思路如下：

• 分：把數(shù)組分成兩半，再遞歸對(duì)子數(shù)組進(jìn)行分操作，直至到一個(gè)個(gè)單獨(dú)數(shù)字
• 合：把兩個(gè)數(shù)合成有序數(shù)組，再對(duì)有序數(shù)組進(jìn)行合并操作，直到全部子數(shù)組合成一個(gè)完整的數(shù)組
  • 合并操作可以新建一個(gè)數(shù)組，用于存放排序后的數(shù)組
  • 比較兩個(gè)有序數(shù)組的頭部，較小者出隊(duì)并且推入到上述新建的數(shù)組中
  • 如果兩個(gè)數(shù)組還有值，則重復(fù)上述第二步
  • 如果只有一個(gè)數(shù)組有值，則將該數(shù)組的值出隊(duì)并推入到上述新建的數(shù)組中

用代碼表示則如下圖所示：

function mergeSort(arr) {  // 采用自上而下的遞歸方法 
    const len = arr.length; 
    if(len < 2) { 
        return arr; 
    } 
    let middle = Math.floor(len / 2), 
        left = arr.slice(0, middle), 
        right = arr.slice(middle); 
    return merge(mergeSort(left), mergeSort(right)); 
} 
 
function merge(left, right) 
{ 
    const result = []; 
 
    while (left.length && right.length) { 
        if (left[0] <= right[0]) { 
            result.push(left.shift()); 
        } else { 
            result.push(right.shift()); 
        } 
    } 
 
    while (left.length) 
        result.push(left.shift()); 
 
    while (right.length) 
        result.push(right.shift()); 
 
    return result; 
} 

上述歸并分成了分、合兩部分，在處理分過程中遞歸調(diào)用兩個(gè)分的操作，所花費(fèi)的時(shí)間為2乘T(n/2)，合的操作時(shí)間復(fù)雜度則為O(n)，因此可以得到以下公式：

總的執(zhí)行時(shí)間 = 2 × 輸入長(zhǎng)度為n/2的sort函數(shù)的執(zhí)行時(shí)間 + merge函數(shù)的執(zhí)行時(shí)間O(n)

當(dāng)只有一個(gè)元素時(shí)，T(1) = O(1)

如果對(duì)T(n) = 2 * T(n/2) + O(n)進(jìn)行左右 / n的操作，得到 T(n) / n = (n / 2) * T(n/2) + O(1)

現(xiàn)在令 S(n) = T(n)/n，則S(1) = O(1)，然后利用表達(dá)式帶入得到S(n) = S(n/2) + O(1)

所以可以得到：S(n) = S(n/2) + O(1) = S(n/4) + O(2) = S(n/8) + O(3) = S(n/2^k) + O(k) = S(1) + O(logn) = O(logn)

綜上可得，T(n) = n * log(n) = nlogn

關(guān)于歸并排序的穩(wěn)定性，在進(jìn)行合并過程，在1個(gè)或2個(gè)元素時(shí)，1個(gè)元素不會(huì)交換，2個(gè)元素如果大小相等也不會(huì)交換，由此可見歸并排序是穩(wěn)定的排序算法

三、應(yīng)用場(chǎng)景

在外排序中通常使用排序-歸并的策略，外排序是指處理超過內(nèi)存限度的數(shù)據(jù)的排序算法，通常將中間結(jié)果放在讀寫較慢的外存儲(chǔ)器，如下分成兩個(gè)階段：

• 排序階段：讀入能夠放進(jìn)內(nèi)存中的數(shù)據(jù)量，將其排序輸出到臨時(shí)文件，一次進(jìn)行，將帶排序數(shù)據(jù)組織為多個(gè)有序的臨時(shí)文件
• 歸并階段：將這些臨時(shí)文件組合為大的有序文件

例如，使用100m內(nèi)存對(duì)900m的數(shù)據(jù)進(jìn)行排序，過程如下：

• 讀入100m數(shù)據(jù)內(nèi)存，用常規(guī)方式排序
• 將排序后的數(shù)據(jù)寫入磁盤
• 重復(fù)前兩個(gè)步驟，得到9個(gè)100m的臨時(shí)文件
• 將100m的內(nèi)存劃分為10份，將9份為輸入緩沖區(qū)，第10份為輸出緩沖區(qū)
• 進(jìn)行九路歸并排序，將結(jié)果輸出到緩沖區(qū)
  • 若輸出緩沖區(qū)滿，將數(shù)據(jù)寫到目標(biāo)文件，清空緩沖區(qū)
  • 若緩沖區(qū)空，讀入相應(yīng)文件的下一份數(shù)據(jù)

參考文獻(xiàn)

https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015

https://chowdera.com/2021/09/20210920201630258d.html#_127

https://juejin.cn/post/6844904007899561998