MergeSort递归解释

Question

我知道这个问题被问了很多次，有很多有用和好的答案，但我有一个关于递归的具体问题。当我们多次递归地调用排序时，到底会发生什么？示例：int[] intArr = {16, 12, 9, 3, 19};当我们将数组分成两个部分或使用两个索引查看它时，merge()对这两个未排序的部分做了什么？我的意思是，在第一次迭代中，前两个半部分没有排序，对吗？方法应该以当前的顺序到达merge()：merge({16, 12}, {9, 3, 19})

public static int[] sort(int l, int r) { 
     
    if (l < r) { 
        int q = (l + r) / 2; 
         
        sort(l, q); 
        sort(q + 1, r); 
        merge(l, q, r); 
    } 
    return intArr; 
} 

我不知道问题是什么，但我没有完全理解合并排序背后的递归。这是一个基本的理解，但是merge()-method给我带来了困难。

Answer 1

当您为sort(0, 4)调用intArr = {16, 12, 9, 3, 19}时，您将再次调用sort(0, 2)，然后是sort(0, 1)，最后是sort(0, 0)。当您到达该值时，l < r将不再为true，并且您将返回不变的数组，因为一个元素的数组已经排序了16。因此，我们回到了对sort(0,1)的调用，因此下一件事是对sort(1,1)的调用，其中l < r不再为true，您将返回不变的数组，因为12是一个单一元素，因此已经排序了。只有这样，您才会到达第一个merge(0, 1)调用，该调用将接受{16, 12, 9, 3, 19}并将所有值从0排序到1，因此结果将是(假定升序) {12, 16, 9, 3, 19}。注意，我们从merge(0, 1)中调用两个排序数组(左和右)。然后，我们已经完成了sort(0, 1)调用，并回到了以前的sort(0, 2)调用，现在调用了sort(2, 2)。这将返回不变的数组，因为l < r不再为真，我们将使用数组{12, 16, 9, 3, 19}继续到merge(0, 2)。调用的结果将是{9, 12, 16, 3, 19}，我们已经完成了sort(0, 2)并移到了sort(0, 4)等等。

我建议您通过您的程序进行调试(或者打印sort()调用的索引)，您将看到第一个merge()调用只在对sort()的几次调用之后发生，并且它只会被调用到已经从它左右排序的数组中。

也可能值得在一些文件上这样做，这样你就可以得到这个概念。

16 12 9 3 19    Sort(0, 4)
16 12 9 | 3 19  Sort(0, 2)
16 12 | 9 3 19  Sort(0, 1)
16 | 12 9 3 19  Sort(0, 0)
^sorted 
16 | 12 9 3 19  Sort(1, 1)
      ^sorted 
12 16 | 9 3 19  Merge(0, 1)
  ^sorted
12 16 | 9 3 19  Sort(2, 2)
        ^sorted
9 12 16 | 3 19  Merge(0, 2)
   ^sorted
9 12 16 | 3 19  Sort(3, 4)
9 12 16 3 | 19  Sort(3, 3)
        ^sorted
9 12 16 3 | 19  Sort(4, 4)
             ^sorted
9 12 16 | 3 19  Merge(3, 4)
           ^sorted
3 9 12 16 19    Merge(0, 4)
all sorted          

Answer 2

想当然，当sort(i, j)返回时，数组将在[i..j]中排序。

现在，sort(l, q)返回array[l..q]排序，sort(q+1, r)返回array[q+1, r]排序。然后，merge(l, q, r)将两个排序子数组交织在一个单独的子数组中，从而使array[l, r]变得排序(合并两个排序数组是一项简单的操作)。

因此，mergesort对越来越大的数组进行排序。

注意，当l==r时，函数会立即返回，因为单个元素的数组是强制排序的。