下面是按身高从矮到高排好队的男生和女生，现在不分男女，只按身高从矮到高排队，如何才能最快排好队呢？

男生：135,137,138,140,140,141,141,141,142,142,143,145

女生：136,139,141,141,142,142,142,143,143,144,144,147

　　很容易，按身高从两队中先后出队到新队中就行了。这个方法就是合并排序方法。

　　程序代码：

　　运行结果：

　　如果原来男女生都没有排好队，那分别排队是不是可以用类似的方法呢？即都分开两组，排好队后合并排序。当然可以，但问题是分开的两组还是没有排好队，所以还不能直接并队。难不倒的，继续分组，直到两组中每组都只有1人就可以了。这就是递归分组方法。递归分组方法和合并排序合起来就是归并排序了。

　　归并排序的时间复杂度（平均）是O(nlog2n)、空间复杂度是O(n)，为不稳定排序算法。比如：待排序数组arr=[8,4,5,7,1,3,6,2]，用归并排序算法对这个数组做排序的图解分析如下图所示。

　　归并排序中先把一个长数组逐步分割成小数组，然后把小数组先排序，再把排好序的小数组两两合并（两个有序数组合并成一个有序数组，用左右指针法），逐步递归，最终完成整个数组的排序。

　　程序代码：

　　运行结果：

　　递归分组和合并排序糅合在一起，程序具体运行步骤与原理图是不一样的。实际的执行过程类似于二叉树中序遍历：开始左树压栈后，又把左树的左树压栈，直到分组只有1个元素，然后产生只有一个元素的右分组，执行合并排序成为有2个元素的有序数组，压栈；然后产生有2个元素的右分组，但这个分组的元素还没排序，压栈后，分只有1元素的左分组，然后产生只有1元素的右分组，合并排序也得到2个元素的有序数组；与刚才的2个元素的有序数组合并成有4个元素的有序数组，压栈；然后产生有4个元素的右分组，……

　　从这个排序的过程可知，最终分组，每组只有1个元素，因此可以一次性分组成最终分组，即每组1个元素，两两合并排序后形成的分组放在一个收集器中，完成后，又以收集器为原分组，继续两两合并，直到只有一个分组为止，这个分组就是排序结果。循环法的也是不稳定排序，时间和空间复杂度不变。

　　程序代码：

　　结果完全一样。

　　练习题１：下面是一些单词，用上面两种归并排序法进行排序（字典顺序），比较结果是否相同。

only a spade and apple seed and all the time plant apple seed big tree  come little seed this time many people need tree too are people with house them give him

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社