归并排序（MERGE-SORT）采用了分治法的思想。分而治之，无限划分，直至最小单元。

时间复杂度        空间复杂度        稳定性
平均O（nlog2n） 最好O（nlog2n） 最坏O（nlog2n）        O(1)        稳定
Python:

def MergeSort(lists):
        if len(lists) <= 1:
                return lists
        num=int(len(lists)/2)
        left=MergeSort(lists[:num])
        right=MergeSort(lists[num:])
        return Merge(left,right)
def Merge(left,right):
        result=[]
        l,r=0,0
        while l<len(left) and r<len(right):
                if left[l]<right[r]:
                        result.append(left[l])
                        l+=1
                else:
                        result.append(right[r])
                        r+=1
        result+=left[l:]
        result+=right[r:]
        return result

print(MergeSort(sorted(range(9),reverse=True)))
---------------------
作者：yangsong95
来源：CSDN
原文：https://blog.csdn.net/yangsong95/article/details/82850761
版权声明：本文为博主原创文章，转载请附上博文链接！