Java에서 병합 정렬을 잘못 구현하는 이유는 무엇입니까?

Question

나는 자바와 알고리즘을 동시에 배우고있다. 이 클래스에서 병합 정렬을 구현했습니다.

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 값과 비교하는 모든 장소를 확인하십시오.