合并排序中的逻辑流程

Question

如何阅读和理解合并代码？我试图使用调试来跟踪逻辑，但它似乎仍然很难弄清楚。你能帮我解释一下吗？非常感谢

static void sort(int[]array, int[] helper, int lower, int upper){ 
     if(lower == upper){ 
      return; 
     } 
     // 6,5,3,1,8,7,2,4 
     int mid = lower + (upper - lower)/2; 
     sort(array, helper, lower, mid); 
     sort(array, helper, mid+1, upper); 

     merge(array, helper, lower, mid+1, upper); 

    } 

Answer 1

下面是一个实时排序数组的图片，同时显示了一个排序图。这些都在wikipedia merge sort page上。

您不仅应该研究排序函数，还应该研究合并函数。排序函数是函数的递归部分，而合并函数是肉和土豆;它的分类部分实际上是什么。

例如，在下面的第一张图片中，排序函数是将块分成4,2和1组。合并函数是对这些块进行排序，比较每个组的第一个值（大小为1，2，然后是4），然后将它们从最低到最高放入新的合并数组中。

Answer 2

下面是一些评论。也看看这个视频，它可以帮助你了解发生了什么。要记住的主要是这是一个递归算法，所以你可以通过将其分解成更小的部分并在这些较小的部分上运行相同的算法来解决它。

static void sort(int[]array, int[] helper, int lower, int upper){   
     if(lower == upper){ 
      // Lower == upper, this means there is only one element, so by definition this is sorted, nothing to do just return 
      return; 
     } 

     // Okay, we have more then one element if we are here. Our goal here is to sort both the upper half, and lower half independently first. 
     // 
     // First find the mid point between the upper and lower bounds we are sorting 
     // For example if we have an array [6, 5, 3, 1, 8, 7, 2, 4] with lower == 0 and upper == 7 then the mid point is 3 
     // Find the mid-point of lower and upper. This will be used to 
     int mid = lower + (upper - lower)/2; 

     // Now sort both the upper and lower half of the array recursively. 
     // Array will look like this to begin with [6, 5, 3, 1, 8, 7, 2, 4] 
     sort(array, helper, lower, mid); 
     // After sorting from 0 to 3 it will look like this 
     // [1, 3, 5, 6, 8, 7, 2, 4] 
     sort(array, helper, mid+1, upper); 
     // After sorting from 4 to 7 it will look like this 
     // [1, 3, 5, 6, 2, 4, 7, 8] 

     // Finally merge the two sorted arrays together. This is easier now the two halfs are sorted. 
     merge(array, helper, lower, mid+1, upper); 
     // After we have a sorted array 
     // [1, 2, 3, 4, 5, 6, 7, 8] 
}