合併排序中的邏輯流程

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