归并排序算法

归并排序的基本思路如下：

1. 分：将序列一份为二，一份为左，一份为右
2. 治：将左归并排序，将右归并排序
3. 合：将左右合并称一个序列

是不是很简单？但是是不是又很奇怪，为什么归并排序会奏效？初学者往往会不理解第二步，为什么第二步可以将序列排序？这里其实忽略了一个细节，这个细节是，如果序列只有一个元素，那么该序列是有序的，也就是说，如果左或者右只有一个元素，那么第二步和第三步是可以省略的。。。这是一个坑，初学者本来对递归的思路有一点模糊的概念，如果再省略掉这个细节，那么上述的论述就是一个无解的结论，所以他们会对第二步产生怀疑！！！当你熟悉这种思维模式之后，你会发现你也会省略掉这个细节，因为这个细节在编码的时候必须考虑，这是递归的终止条件（同时也是归纳法的基础）
现在，还有一个问题，就是如果理解这个递归？递归从某种意义上说就是数学归纳法的体现，数学归纳法是一个很自然的算法思想，如果你非要细究什么是归纳，这就像你怀疑为什么三角形的三个角的和是180度！！！是不是觉得奇怪，如果按照这个推论，递归应该是一个很自然的思维方式了，没错，你没想错，递归是一种很自然的思维方式，如果你能体会到这种自然，很多的算法你都会迎刃而解，再也不用纠结算法的描述，因为那些算法的描述很繁杂，繁杂到你会怀疑你自己的智商，但是那些算法真的很自然，你也可以理解，有些自然的东西是很难描述清楚的，毕竟我们的语言不是上帝的语言！！！
在啰嗦一句，上面的“分，治，合”是一个经典的思维模式，这是分治法思想的核心，如果有时间，我会单独的对这个思想进行论述。

代码1如下:

def merger_sort(L, l, h):
    if h - l == 1:
        return

    m = (l + h) >> 1
    merger_sort(L, l, m)
    merger_sort(L, m, h)
    merger(L, l, m, h)
    return L

代码1就是合并算法的步骤了，是不是很简单，你会发现其中的merger算法并没有实现，因为这是合并排序的核心算法，merger的算法如代码2。
代码2如下：

def merger(L, l, m, h):
    L1 = L[l:m]
    L2 = L[m:h]
    i = 0
    j = 0
    k = l
    while True:
        if i >= m - l and j >= h - m:
            break
        elif i >= m - l:
            L[k] = L2[j]
            k += 1
            j += 1
        elif j >= h - m:
            L[k] = L1[i]
            k += 1
            i += 1
        else:
            if L1[i] <= L2[j]:
                L[k] = L1[i]
                k += 1
                i += 1
            else:
                L[k] = L2[j]
                k += 1
                j += 1

merger的实现方式有很多种，但是无外乎代码2的形式，代码2的形式是我对merger算法的第一反应，你会发现我喜欢使用 "while True"语句，因为我对循环的理解就是一个无限循环执行的机器，除了机器内部出现某种故障，不然这个机器会一直运行下去，这个故障就是循环的终止条件，我会用break语句终止这个循环，你可以将break语句的条件设置成循环的终止条件，不过这不是我认识这个世界的方式，或许你看不懂我的这种方式，但是，这的确是我的第一反应，珍惜这种反应，因为这种反应对你是最自然的。