归并排序

    作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

    • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
    • 自下而上的迭代；

    在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

    说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。

    和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

    2. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

    3. 重复步骤 3 直到某一指针达到序列尾；

    4. 将另一序列剩下的所有元素直接复制到合并序列尾。

    3. 动图演示

    5. Python 代码实现

    7. Java 代码实现