[[428236]]

本文轉載自微信公眾號「JS每日一題」，作者灰灰。轉載本文請聯系JS每日一題公眾號。

一、是什么

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

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

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

然后進行兩兩合并，使 n 個有序表變為n/2 個長度為 2 或者 1 的有序表(例如 4 個小有序表合并為 2 個大的有序表)

通過不斷地進行兩兩合并，直到得到一個長度為 n 的有序表為止

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

如下圖所示：

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

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

二、如何實現

關于歸并排序的算法思路如下：

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

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

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; 
} 

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

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

當只有一個元素時，T(1) = O(1)

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

現在令 S(n) = T(n)/n，則S(1) = O(1)，然后利用表達式帶入得到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

關于歸并排序的穩定性，在進行合并過程，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也不會交換，由此可見歸并排序是穩定的排序算法

三、應用場景

在外排序中通常使用排序-歸并的策略，外排序是指處理超過內存限度的數據的排序算法，通常將中間結果放在讀寫較慢的外存儲器，如下分成兩個階段：

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

例如，使用100m內存對900m的數據進行排序，過程如下：

• 讀入100m數據內存，用常規方式排序
• 將排序后的數據寫入磁盤
• 重復前兩個步驟，得到9個100m的臨時文件
• 將100m的內存劃分為10份，將9份為輸入緩沖區，第10份為輸出緩沖區
• 進行九路歸并排序，將結果輸出到緩沖區
  • 若輸出緩沖區滿，將數據寫到目標文件，清空緩沖區
  • 若緩沖區空，讀入相應文件的下一份數據

參考文獻

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