Наверху down mergesort. Операция слияния нечеткая

Question

Я узнаю о слиянии сверху вниз, и я начинаю понимать рекурсивную часть. Я видел пару реализаций, где слияние было выполнено с помощью цикла 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 использует только один цикл вместо трех циклов, используемых в большинстве реализаций (по крайней мере, для большинства реализованных реализаций).

Первые два условия обрабатывают случаи, когда все элементы из одного из двух объединяемых массивов источников уже добавлены в объединенный массив. Эти условия обычно обрабатываются отдельными циклами, которые следуют за первым циклом, и не требуют сравнения элементов из двух исходных массивов.

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