4.4 合并排序算法
合并排序法是针对已经排好序的两个或两个以上的数列，通过合并的方式，将其组合成一个有序的大数列。使用合并排序法为一个数列排序时，首先将无序的数列分成若干小份，分若干份的规则就是不断把每段长度除以2（对半分），直到分到不能再分为止（当数列中最多只有两个元素时视为不可再分），然后对最小份进行排序，最后再逐步合并成一个有序的大数列，如图4.25所示。
图4.25 合并排序法工作原理
例如，有这样一组数据：33, 10, 49, 78, 57, 96, 66, 21，如图4.26所示。对其递增排序，步骤如下。
图4.26 无序的原始值
（1）将原始数列一分为二，得到两个数列，即数列1和数列2，数列1为33, 10, 49, 78；数列2为57, 96, 66, 21，如图4.27所示。
图4.27 将数列分为两个数列
（2）将数列1和数列2再一分为二，得到数列a、数列b、数列c和数列d，即每个数列中包含两个数据，并将每份中的两个数据进行排序，如图4.28所示。
图4.28 将4个数列中的数据分别排序
（3）合并排好序的数列元素。将数列a与数列b合并为数列A，数列c与数列d合并为数列B，再对数列A和数列B中的元素分别进行排序，如图4.29所示。
图4.29 将数列合并为两个数列并排序
（4）将数列A与数列B合并为一个数列，并对其中的元素排序，最终排序结果如图4.30所示。
图4.30 将数列合并为一个数列并排序
【实例4.7】 使用合并排序法将列表中的数字递增排序。（实例位置：资源包\Code\04\07）
用Python代码实现上方示例中的合并排序算法，具体代码如下：
运行结果如图4.31所示。
图4.31 合并排序法
【实例4.8】 争夺十二生肖。（实例位置：资源包\Code\04\08）
很久以前，玉帝决定在人间选拔12种动物作为生肖，他定好一个日子，动物们都来报名，先到的12种动物将成为十二生肖。利用合并排序法根据12种动物到达的时间（如数字6.25代表6:25到达），对十二生肖顺序进行排序。具体代码如下：
运行结果如图4.32所示。
图4.32 运行结果