归并排序

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

归并排序是经典的外部排序之一，常见的外部排序：二路归并

(39条消息) 数据结构---归并排序和外部排序_归并排序 外部排序_boke_fengwei的博客-CSDN博客

算法实现

一、归并排序

下面提到的merge函数见第二节

由底至顶直接排序

def MergeSort1(arr, n): #由底至顶
    if n>0:
        i = 1
        while i<=n : #先从1开始，每次增加i。即归并块
            j=0
            while j
                merge(arr, j, j+i-1, min(j+i+i-1, n-1))
                j += 2*i
            i+=i

递归法

注意递归法需要找到数组中点，因此比较不适合链表排序