CS161 Lecture 4 Merge Sort

CS161

Merge sort 特点

Merge Sort（归并排序）是除了heapsort外另一个复杂度为O($n\log n$)的排序方法。比起heapsort，merge sort有很多优点：

• 更简单
• 原本是为大量数据和流数据设计的排序方法
• 更少的比较次数，这一点在元素比较成本更为昂贵的时候很有用
• 不是在原地比较的算法，需要创建新array，对额外空间有要求。

Divide-and-conquer

Merge sort还是一个典型的分治法思想算法。分治法的基本步骤是：

• 将输入分成几个对同一类型输入的子问题，子问题的输入更少。如两个子问题，那么每个子问题的输入应为本来问题的一半。
• 递归地解决这些子问题
• 合并结果

伪代码

def mergesort(input):
    n = len(input)
    if n < 2:
        return input
    left = mergesort(input[ :n//2])
    right =  mergesort(input[n//2: ])
    i = 0
    j = 0
    output = []
    while i<len(left) and j<len(right):
        if left[i] <= right[j]:
            output.append(left[i])
            i += 1
        else:
            output.append(right[j])
            j += 1
    while i<len(left):
        output.append(left[i])
        i += 1
    while j<len(right):
        output.append(right[j])
        j += 1
    return output

分析

line 3,4：recursion base case。
line 5,6：divide and recursion，将原本输入分为长度为$\lfloor \frac{n}{2}\rfloor$和$\lceil \frac{n}{2} \rceil$的两个部分，分别recurse。
line 7,8：归零指向左右的指针，准备merge，此时左和右两个队列内部都是已排序的，因为是递归的产物。
line 10~16：在指针指的位置比较，二者取小，直到其中一个队列为空。
line 17~22：剩余的非空队列剩下的肯定都是大数，直接加入队尾。
更深入的参考

Master Method

是一种常用于Divide and conquer问题的分析法。见专文。