了解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]

现在已经分类了