自上而下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++]; 
     }