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所示。