自上而下mergesort。合併操作不明確

Question

我正在學習自頂向下mergesort，我開始理解遞歸部分。我已經看到了幾個實現了一系列while循環的合併。

但是，在下面的實現中，合併操作是不同的，它並不清楚它是如何工作的。這似乎只是比較指標，而不是實際的元素（不像其他實現我見過）

 private void merge(int[] aux, int lo, int mid, int hi) { 

     for (int k = lo; k <= hi; k++) { 
      aux[k] = theArray[k]; 
     } 

     int i = lo, j = mid+1; 
     for (int k = lo; k <= hi; k++) { 
      if (i > mid) { 
       theArray[k] = aux[j++]; 
      } 
      else if (j > hi) { 
       theArray[k] = aux[i++]; 
      } 
      else if (aux[j] < aux[i]) { 
       theArray[k] = aux[j++]; 
      } 
      else { 
       theArray[k] = aux[i++]; 
      } 
     } 
    } 

    private void sort(int[] aux, int lo, int hi) { 
     if (hi <= lo) 
      return; 
     int mid = lo + (hi - lo)/2; 
     sort(aux, lo, mid); 
     sort(aux, mid + 1, hi); 
     merge(aux, lo, mid, hi); 
    } 

    public void sort() { 
     int[] aux = new int[theArray.length]; 
     sort(aux, 0, aux.length - 1); 
    } 

上面的代碼假定全局變量theArray存在。

Answer 1

這merge方法只是簡單地使用一個循環，而不是大多數實現中使用的3個循環（至少大多數我見過的實現）。

前兩個條件處理來自兩個源數組之一合併的所有元素已經添加到合併數組的情況。這些條件通常由第一個循環後面的單獨循環處理，而不需要比較兩個源數組中的元素。

 if (i > mid) { // all the elements between lo and mid were already merged 
         // so all that is left to do is add the remaining elements 
         // from aux[j] to aux[hi] 
      theArray[k] = aux[j++]; 
     } 
     else if (j > hi) { // all the elements between mid+1 and hi were already merged 
          // so all that is left to do is add the remaining elements 
          // from aux[i] to aux[mid] 
      theArray[k] = aux[i++]; 
     } 
     else if (aux[j] < aux[i]) { // both source arrays are not done, so you have to 
            // compare the current elements of both to determine 
            // which one should come first 
      theArray[k] = aux[j++]; 
     } 
     else { 
      theArray[k] = aux[i++]; 
     }