Java Merge排序算法:是什么让Merge方法在完成初始singleton元素合并后在更大的元素集上递归运行

Question

基本上一切都在问题本身，我得到了一些运行良好的代码，但其逻辑对我来说并不完全清楚。

更详细地说：

分析Merge sort的一个实现时，我遇到了一个概念问题，即当合并排序应用程序合并了最初的一组项（两个单例元素）后，使其继续合并的语句究竟是什么？

到目前为止，我没有看到任何东西可以阻止程序在第一次合并后立即停止执行。是什么命令应用程序继续？

举例说明：

1. divideMethod
    {
    return the array 
    if the it has less than 2 elements
    { divide into 2 parts,
    divide (1st recursion) on the left half,
    divide (1st recursion)  on the right half,
    mergeMethod(so-called 2nd or inversed recursion) on left and right   halves,
    return the array
    }   
    } 
2. mergeMethod

我没有粘贴原始代码以使插图尽可能简洁

为了防止任何误解，Merge排序的原则对我来说很清楚：

1-将数组（或任何其他变量集）划分为单例元素对，

2-比较并合并这些元素，然后

3-在比较较大的预编序元素集的同时，重新组合返回数组。

但是，一旦完成了对singleton元素的划分和主合并排序（成对进行排序），我就看不出是什么让代码再次重复合并，并将所有这些小对重新组合成更大的对（4、8、16项等等），最终组成一个完整的排序数组。

这种第二次（逆）递归从哪里来，第一次是（如上所述）对初始数组的除法？

该算法是用Java实现的，但这个问题显然不是任何特定编程语言所特有的。

Answer 1

我想您对递归有一个问题。

divideMethod
    {
    return the array 
    if the it has less than 2 elements
    { divide into 2 parts,
    divide (1st recursion) on the left half,
    divide (1st recursion)  on the right half,

创建深度调用堆栈。当调用内部除法时，外部除法不会完成。它仍然有的合并要做。而外部的除法有的合并要做

和往常一样，使用调试器（与Eclipse等IDE一起内置）进行调试，然后自己查看。

Answer 2

自上而下的合并排序先左后深。使用|表示数组的拆分：

    |7 6 5 4 3 2 1 0|
    |7 6 5 4|3 2 1 0|
    |7 6|5 4|
    |7|6|
    |6 7|
        |5|4|
        |4 5|
    |4 5 6 7|
            |3 2|1 0|
            |3|2|
            |2 3|
                |1|0|
                |0 1|
            |0 1 2 3|
    |0 1 2 3 4 5 6 7|

自下而上的合并排序是广度优先，左侧优先。它跳过将大小为n的数组处理为n次的递归拆分大小为1，使用迭代更新索引和运行大小：

    |7 6 5 4 3 2 1 0|
    |7|6|5|4|3|2|1|0|
    |6 7|
        |4 5|
            |2 3|
                |0 1|
    |4 5 6 7|
            |0 1 2 3|
    |0 1 2 3 4 5 6 7|