导论第二章再讲时间复杂度的计算，通过写插入排序( 插入排序与循环不变式 )讲了循环的时间复杂度的计算，而接着通过归并排序介绍分治法以及分治法的时间复杂度。

A = [2, 5, 1, 3, 7, 6]

def merge_sort(nums, start, end):
    if end <= start + 1:
        return nums
    m = (start + end ) / 2
    merge_sort(nums, start, m)
    merge_sort(nums, m, end) # not m + 1

    l_nums = nums[start:m]
    r_nums = nums[m:end]
    l_nums_len = len(l_nums)
    r_nums_len = len(r_nums)
    s = j = 0
    for i in range(start, end):
        if s < l_nums_len and j < r_nums_len:
            if l_nums[s] < r_nums[j]:
                nums[i] = l_nums[s]
                s += 1
            else:
                nums[i] = r_nums[j]
                j += 1
        else:
            break

    while i < end:
        if s < l_nums_len:
            nums[i] = l_nums[s]
            s += 1
        if j < r_nums_len:
            nums[i] = r_nums[j]
            j += 1
        i += 1

    return nums

我实现的代码可能不是很 pythonic，甚至也和导论中给出的伪代码有些区别。

在这里踩得坑是注释的地方，在我执行完 merge_sort(nums, start, m) 之后，想当然的执行了 merge_sort(nums, m + 1, end)，其实这是不对的，因为这里的区间是 [start, end)，如果在运行左边部分的时候，使用 m + 1，那么在 m 那个位置上的值将被忽略掉。