归并排序（Merge Sort）:

归并排序是一个相当“稳定”的算法对于其它排序算法，比如希尔排序，快速排序和堆排序而言，这些算法有所谓的最好与最坏情况。而归并排序的时间复杂度是固定的，它是怎么做到的？

两个有序数组的合并：

首先来看归并排序要解决的第一个问题：两个有序的数组怎样合成一个新的有序数组：

比如数组1｛ 3，5，7，8 ｝数组2为｛ 1，4，9，10 ｝：

首先那肯定是创建一个长度为8的新数组咯，然后就是分别从左到右比较两个数组中哪一个值比较小，然后复制进新的数组中：比如我们这个例子：

｛ 3，5，7，8 ｝ ｛ 1，4，9，10 ｝ ｛ ｝一开始新数组是空的。

然后两个指针分别指向第一个元素，进行比较，显然，1比3小，所以把1复制进新数组中：

｛ 3，5，7，8 ｝ ｛ 1，4，9，10 ｝ ｛ 1， ｝

第二个数组的指针后移，再进行比较，这次是3比较小：

｛ 3，5，7，8 ｝ ｛ 1，4，9，10 ｝ ｛ 1，3， ｝

同理，我们一直比较到两个数组中有某一个先到末尾为止，在我们的例子中，第一个数组先用完。｛ 3，5，7，8 ｝ ｛ 1，4，9，10 ｝ ｛ 1，3，4，5，7，8 ｝

最后把第二个数组中的元素复制进新数组即可。

｛ 1，3，4，5，7，8，9，10 ｝

由于前提是这个两个数组都是有序的，所以这整个过程是很快的，我们可以看出，对于一对长度为N的数组，进行合并所需要的比较次数最多为2 * N -1。

这其实就是归并排序的最主要想法和实现，归并排序的做法是:

将一个数组一直对半分，问题的规模就减小了，再重复进行这个过程，直到元素的个数为一个时，一个元素就相当于是排好顺序的。

接下来就是合并的过程了，合并的过程如同前面的描述。一开始合成两个元素，然后合并4个，8个这样进行。

所以可以看到，归并排序是“分治”算法的一个经典运用。

我们可以通过代码来看看归并算法的实现：

def merge_sort(lst):
    if len(lst) <=1:
        # 列表长度为1时，无法再拆分，直接返回
        return lst  
    mid = len(lst)/2
    #通过不断递归，将原始列表拆分成n个小列表111
    left = merge_sort(lst[:int(mid)]) 
    right = merge_sort(lst[int(mid):])
    return merge(left,right)

def merge(left,right):
    i,j=0,0
    result=[]
    # 比较传入的两个子列表，对两个子列表进行排序
    while i<len(left) and j<len(right): 
        if left[i] <= right[j]:
            result.append(left[i])
            i+=1
        else:
            result.append(right[j])
            j+=1
    # 将排好序的子列表合并
    result.extend(left[i:]) 
    result.extend(right[j:])
    return result

if __name__ == "__main__":
    rand_lst=[1,5,2,5,6,1]
    print(merge_sort(rand_lst))