MergeSort. Ошибка в логике слияния

Question

Может ли кто-нибудь сказать, в чем проблема в логике слияния? Если элемент правого массива меньше элемента в левом массиве, то он работает. Другой мудрый дает неправильный ответ. Я правильно разделил массив. Я даю свою логику слияния здесь.

public static void main(String[] args) { 
    int[] list = { 32,14, 67, 76, 23, 41, 58, 85}; 
    System.out.println("before: " + Arrays.toString(list)); 
    mergeSort(list); 
    System.out.println("after: " + Arrays.toString(list)); 
} 

public static void mergeSort(int[] array) { 
    if (array.length > 1) { 
     // split array into two halves 
     int[] left = leftHalf(array); 
     int[] right = rightHalf(array); 

     mergeSort(left); 
     mergeSort(right); 

     merge(array, left, right); 

    } 
} 


public static void merge(int[] result, 
     int[] left, int[] right) { 
    int i1 = 0; // index into left array 
    int i2 = 0; // index into right array 
    int j = 0; 
    int k = 0; 
    for (int i=0; i1 < left.length && i2 < right.length;i++) { 
     if (left[i1] < right[i2]) { 
      result[i] = left[i1]; 
      // take from left 
      i1++; 
     } else { 
      result[i] = right[i2]; 
      // take from right 
      i2++; 
     } 
    } 
} 

Answer 1

У вас есть два неиспользуемых переменных j и k в вашем коде. Ваша логика ошибочна, потому что вы копируете в массив до тех пор, пока одна половина не будет пуста, поэтому вы никогда не освободите обе половины.

public static void merge(int[] result, int[] left, int[] right) { 
    int i1 = 0; // index into left array 
    int i2 = 0; // index into right array 
    int i; 
    for (i = 0; i1 < left.length && i2 < right.length;i++) { 
     if (left[i1] < right[i2]) { 
      result[i] = left[i1++]; 
      // take from left 
     } else { 
      result[i] = right[i2++]; 
      // take from right 
     } 
    } 
    for (; i1 < left.length; i++) result[i] = left[i1++]; 
    for (; i2 < right.length; i++) result[i] = right[i2++]; 
} 

только один из двух для петель будут работать в конце, и будет обрабатывать то, что осталось от другой половины.