[Algorithmic Toolbox学习笔记][week4]Merge Sort

Merge Sort是如何工作的？

第一步：拆

拆即将数列一分为二，直到拆分到最小单元（个位数）

第二步：合

合即将两个已经排好序的数列合并为一个数列。
先准备一个空数列D，然后将数列B和C的第一个数进行比较，比较完成后将较小的数加入到新数列D中同时把这个数从原数列中去除。然后继续重复刚刚的步骤比较B和C，直到其中一个数列为空。

Merge Sort的代码实现

# in python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2

    left = arr[:mid] #up to but not inclide mid
    right = arr[mid:]

    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)

    return merge(left_sorted,right_sorted)

def merge(a, b):
    # a and b are sorted
    empty_arr = []

    while len(a)>0 and len(b)>0:
        if a[0] <= b[0]:
            empty_arr.append(a[0])
            a.pop(0)

        else:
            empty_arr.append(b[0])
            b.pop(0)

    empty_arr += a
    empty_arr += b

    return empty_arr

list = [17, 9, 25, 5, 89, 71, 63, 45, 59, 23]
print(merge_sort(list))

Merge Sort的运行速度

由于merge数列B和数列C的运行时间是 O(n)，每次sort的时候都要调用两次方法且每次参与排序的数字的数量都为之前的一半，那么我们可以知道：

根据The Master Theorem我们可以知道：