介紹

歸并排序（英語：Merge sort），是創建在歸并操作上的一種有效的排序算法，效率為    。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行^[1]。

采用分治法:

• 分割：遞歸地把當前序列平均分割成兩半。
• 合并：在保持元素順序的同時將上一步得到的子序列合并到一起（歸并）。

圖解算法

看完上面的定義，如果你感到有點懵，那就對了本文就是寫給你的。我們通過圖文來詳細地介紹算法的流程。算法的核心只有4個字分割和合并。

假定我們對下面的序列，按照從小到大進行排序。

94, 45, 82, 33, 25, 59, 94, 65, 23

當然你很快地手動就能完成排序任務，但30萬個數字你可能就會崩潰了。還是先來看這個例子，先將這個序列平均分割。一共有9個數字，取中間位置是4.5，取整的結果為4。分成兩個子序列，前4個元素和后5個元素，然后分別對兩個子序列遞歸操作，直到子序列只有一個元素為止。

上面的步驟完成了分割，接下來開始合并了。最小的兩個子序列是94和45，于是合并這兩個子序列，得到序列[45, 94]，另外的子序列是[33, 82]，于是合并這兩個子序列就得到左半部分[33, 45, 82, 94]。

這里元素較少，你可能并沒有看清楚，就得到了左半部分有序子序列（前4個元素）。同樣的操作我們得到后面5個元素的有序子序列，最后來合并這兩個子序列。下文會詳細說明。

[33, 45, 82, 94]
[23, 25, 59, 65, 94]

合并的過程都是一樣的，下面gif動圖清楚地演示了兩個子序列的合并過程。（由于受公眾號的限制，無法給出完成的演示）。完整演示可以看后面的視頻。

參考代碼

下面是用Python實現的歸并排序算法的代碼，僅供參考：

import typing as t

def sort(data: t.List[int]):
    """
    sort data
    """
    if len(data) <= 1:
        return data
    mid = len(data) // 2 
    left = sort(data[:mid])
    right = sort(data[mid:])
    return merge(left, right)
    
def merge(left: t.List[int], right: t.List[int]):
    """
    merge two list
    """
    i = 0 
    j = 0 
    ret = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            ret.append(left[i])
            i += 1
        else:
            ret.append(right[j])
            j += 1

        if i == len(left):
            ret.extend(right[j:])

        if j == len(right):
            ret.extend(left[i:])
    return ret

if __name__ == '__main__':
    d = [45, 94, 33, 82, 25, 59, 94, 65, 23]
    data = sort(d)
    print(data)