4.4　合并排序算法

合并排序法是針對已經排好序的兩個或兩個以上的數列，通過合并的方式，將其組合成一個有序的大數列。使用合并排序法為一個數列排序時，首先將無序的數列分成若干小份，分若干份的規則就是不斷把每段長度除以2（對半分），直到分到不能再分為止（當數列中最多只有兩個元素時視為不可再分），然后對最小份進行排序，最后再逐步合并成一個有序的大數列，如圖4.25所示。

例如，有這樣一組數據：33, 10, 49, 78, 57, 96, 66, 21，如圖4.26所示。對其遞增排序，步驟如下。

（1）將原始數列一分為二，得到兩個數列，即數列1和數列2，數列1為33, 10, 49, 78；數列2為57, 96, 66, 21，如圖4.27所示。

（2）將數列1和數列2再一分為二，得到數列a、數列b、數列c和數列d，即每個數列中包含兩個數據，并將每份中的兩個數據進行排序，如圖4.28所示。

（3）合并排好序的數列元素。將數列a與數列b合并為數列A，數列c與數列d合并為數列B，再對數列A和數列B中的元素分別進行排序，如圖4.29所示。

（4）將數列A與數列B合并為一個數列，并對其中的元素排序，最終排序結果如圖4.30所示。

【實例4.7】　使用合并排序法將列表中的數字遞增排序。（實例位置：資源包\Code\04\07）

用Python代碼實現上方示例中的合并排序算法，具體代碼如下：

運行結果如圖4.31所示。

【實例4.8】　爭奪十二生肖。（實例位置：資源包\Code\04\08）

很久以前，玉帝決定在人間選拔12種動物作為生肖，他定好一個日子，動物們都來報名，先到的12種動物將成為十二生肖。利用合并排序法根據12種動物到達的時間（如數字6.25代表6:25到達），對十二生肖順序進行排序。具體代碼如下：

運行結果如圖4.32所示。