python3实现归并排序算法图文详解

归并排序做为一种比较经典的排序思路，经常在面试中被提及。即使不直接考察也会换种方式涉及，例如很常见的20G超大文件排序问题。这一节就分解下归并的思路，最后用代码实现一下。下一篇我们进行一下扩展，实现超大文件的排序。

归并排序

归并排序（Merge Sort）的主要思想就是化整为零，分批治理，再逐层合并结果。和快排有些许类似，同样也是递归的典型使用场景。

例如有下面的list

[38,67,26,11,99,20,45,54]

首先是化整为零，分的方法很多，我这里采用对半分

一直分到最后每个list只有单个元素为止，然后按照原先分的list开始从下往上合并。

即使是奇数个元素也是可以对半分的，一直分到最后3个元素分到一边1个一边2个，其中的2个元素再分为两个单元素

每个list分解再合并之后就变成了有序list，拿其中一部分来举例

第二行的两个list经过再合并就变成了如下的有序list，因为从第三行合并到第二行和从第二行合并到第一行的算法是一样的，所以我们就以已经排序完成的第二行到第一行为例来说明

对左右两个list的第一个元素分别放置游标，并且比较俩游标元素的大小，较小的放入新list，并且该侧的游标往右移动一位。因为11比38小，所以将11放入新list，并且right游标往右移动到26。

此时26还是比38小，所以还是将26放入新list，往右移动right游标，但是此时已经无法移动。之后将另一个list的元素全部添加到新list的尾部。

这样就将原先的[38,67,26,11]经过先拆分再合并的方式排序成了[11,26,38,67]。之后该新list又和之前拆分的另一个list进行同样的操作往上合并，一直到最后恢复完整list。

代码实现

要实现的功能，就是传递一个list进去，能返回一个有序list。以上面的图片为例，实现从[38,67,26,11]到[11,26,38,67]。

按照递归的思路，我们这里只需要关心从第二层到第一层的拆分再合并的实现，至于再往下直接用递归操作即可。

将原list拆分为2段，每段经过原函数递归返回俩有序list

def mergeSort(list_):
    list1 = mergeSort(list_[0:len(list_)//2])
    list2 = mergeSort(list_[