java - 理解Java合并排序的排序部分

Question

我理解合并排序的合并部分是如何工作的，但是，由于某种原因，我无法理解调用合并函数之前发生的递归/除法部分。使用下面的示例代码，我尝试跟踪不同变量的值，但无法完全理解发生了什么。

public void sort(int arr[], int l, int r) { 
    if (l < r) 
    { 
        // Find the middle point 
        int m = (l+r)/2; 

        // Sort first and second halves 
        sort(arr, l, m); 
        sort(arr , m+1, r); 

        // Merge the sorted halves 
        merge(arr, l, m, r); 
    } 

}

对我来说，m 似乎一直被传递到 sort 中，直到它变成 0，所以看起来第二个 sort() 调用和 merge() 调用永远不会执行。有人可以解释一下所采取的步骤吗？

Answer 1

采用以下数组:

[4][2][5][1][3]

我们将把它分成两半:

[4][2][5]    [1][3]

再说一遍:

[4][2]    [5]    [1]    [3]

再说一遍:

[4]    [2]    [5]    [1]    [3]

注意我们现在有 5 个排序数组(每个数组的长度为 1)。现在是时候将它们合并在一起并进行排序了。将两个排序数组合并到一个新的排序数组中是一个非常简单的(读取:低时间复杂度)操作:

[2][4]    [1][5]    [3]

现在我们有 3 个排序数组。让我们再次合并它们:

[1][2][4][5]    [3]

最后一次:

[1][2][3][4][5]

现已排序。