Почему моя реализация сортировки слияния в Java заблуждается?

Question

Я изучаю Java и алгоритмы одновременно. Я реализовал сортировку слияния в этом классе.

public class Sorter { 
    private void merge(int [] numbers, int low, int mid, int high) { 
      // create a new array that will contain the merged integers 
      int[] arrIntMerged = new int[high - low + 1]; 

      // set indices 
      int i = low, j = mid + 1, k = 0; 

      // add the lesser integer into merged array 
      while (i <= mid && j <= high) { 
       if (numbers[i] < numbers[j]) { 
        arrIntMerged[k] = numbers[i]; 
        i++; 
       } else { 
        arrIntMerged[k] = numbers[j]; 
        j++; 
       } 
       k++; 
      } 

      // add anything left in the left side of the array 
      while (i <= mid) { 
       arrIntMerged[k] = numbers[i]; 
       i++; 
       k++; 
      } 

      // add anything left in the right side of the array 
      while (j <= high) { 
       arrIntMerged[k] = numbers[j]; 
       j++; 
       k++; 
      } 

      // write this newly created array into the positions in the original array 
      for (int l = 0; l < arrIntMerged.length; l++) { 
       numbers[l + low] = arrIntMerged[l]; 
      } 
     } 

     // recursive implementation 
     private void _mergeSort(int[] numbers, int low, int high) { 
      if (low == high) 
       return; 
      else { 
       // find midpoint while preventing overflow 
       int mid = low + (high - low)/2; 
       // sort left and right side 
       _mergeSort(numbers, low, mid); 
       _mergeSort(numbers, mid + 1, high); 
       // merge both sides 
       merge(numbers, low, mid + 1, high); 
      } 
     } 

     // friendly interface to begin merge sort 
     public void mergeSort(int[] numbers) { 
      _mergeSort(numbers, 0, numbers.length - 1); 
     } 
} 

Я затем осмотрел этот код в записках в Eclipse.

Sorter sorter = new Sorter(); 
int[] nums = {5, 6, 7, 8, 1, 2, 3, 4}; 
sorter.mergeSort(nums); 
System.out.println(Arrays.toString(nums)); 

К сожалению, стандартный вывод читает [2, 3, 4, 5, 6, 7, 8, 1], который вышел из строя. Почему мой тип слияния ошибочен? Я почти уверен в своих граничных условиях в _mergeSort, поэтому я подозреваю, что моя функция merge не работает.

Answer 1

Ваша проблема вытекает из следующего присваивания в merge:

j = mid + 1 

mid уже индекс к первому номеру на правой стороне слияния, этот прирост делает остальную часть вашего слияния логики запуска в неправильная позиция массива.

Потому что, похоже, вы учитесь, я не буду испортить ваш опыт, разместив необходимые изменения кода, но вот подсказка: проверьте все места, где вы сравниваете вещи с значением mid.