思想

将列表进行递归的对半拆分，直到只剩下一个元素。然后，进行合并。
合并的方式可以这样理解：
左右两根管子里面装着数字球（经过排序）。首先比较那个球的数字大，大的一方就倒入一个叫 result 的竖管里。然后后面的数字球补空位。
当某一个管子为空时，另一方全部倒入 result。合并完成。

灵魂画师

注意管子里的数本身要经过排序。如何确保这一点？那就是不停拆分，直到每个小列表只剩一个元素，那么两两合并就可以保证合并的结果是有序的。然后重复此过程，直到所有元素都合并，排序完成。

代码实现

def merge(left, right):
    result = []
    while len(left)>0 and len(right)>0 :
        if left[0] <= right[0]: # 倒数字球的过程
            result.append( left.pop(0) )
        else:
            result.append( right.pop(0) )
    # 剩余的一并倒入
    result += left
    result += right
    return result

def merge_sort( li ):
    # 拆分到只剩一个元素为止
    if len(li) == 1:
        return li
    mid = len(li) // 2
    left = li[:mid]
    right = li[mid:]

    ll = merge_sort( left )
    rl =merge_sort( right )
    return merge(ll , rl)

带着实际的参数我们来走一遍：
[2, 1]
那么 merge_sort 第一次，分成 2 组 (2//2=1)：
[2] 和 [1]
然后递归，再 merge_sort 一次，变成：
左右分别返回 [2], [1] 本身。也就是：
ll = [2]
rl = [1]
然后运行 merge(ll, rl)，把大的吐出来，最后就是结果了。