排序Java合并排序算法：当初始单例元素合并完成后，是什么使得合并方法在更大的元素集上递归运行？

Question

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

更详细地说：

在分析合并排序的一个实现时，我遇到了一个概念性的问题：在合并初始项集（两个单例元素）后，使合并排序应用程序继续合并的语句究竟是什么

至于现在，我看不到任何东西可以阻止程序在第一次合并后立即停止执行。是什么命令应用程序继续

一些用于说明的伪代码：

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

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

为了避免任何误解，我很清楚合并排序的原则：

1-将一个数组（或任何其他变量集）分成若干个单元素对

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

3-重新组合返回数组，同时比较更大的预先排序的元素集

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

这种第二个（逆）递归从何而来，第一个是（正如我上面所描述的）初始数组的除法

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

Answer 1

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

    |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|

Answer 2

我想你对递归有疑问

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中）进行调试，然后亲自查看