Реализация Coreman MergeSort в java не производит корректного вывода

Question

Я пытаюсь реализовать алгоритм MergeSort Coreman в Java. Но это всегда дает мне неправильный вывод.

До сортировки: [86, 8, 60, 9, 49, 73, 37, 59, 98, 69]

После сортировки: [8, 8, 9, 37, 37, 49, 49, 59, 69, 69]

Ниже мой код:

public class MergeSort { 
    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     MergeSort mergeSort = new MergeSort(); 
     int [] data = mergeSort.createRandomNumberArray(); 
     mergeSort.print("Before sorting", data); 
     long startTime = System.currentTimeMillis(); 
     mergeSort.sort(data); 
     long endTime = System.currentTimeMillis(); 
     mergeSort.print("After Sorting", data); 
     mergeSort.time(startTime, endTime); 

    } 

    public void sort(int[] data) { 
     if(data == null) 
      throw new NullPointerException(); 
     if(data.length == 0 || data.length == 1) { 
      System.out.println("Size is " + data.length); 
      return; 
     } 

     int length = data.length; 
     mergeSort(data, 0, length - 1); 
    } 

    /** 
    * @param data 
    * @param first 
    * @param last 
    */ 
    private void mergeSort(int[ ] data, int first, int last) { 
     if(first < last) { 
      int middle = (first + last)/2; 
      mergeSort(data, first, middle); 
      mergeSort(data, middle + 1, last); 
      merge(data, first, middle, last); 
     } 
    } 

    private void merge(int[ ] data, int first, int middle, int end) {  
     int lSize = middle - first + 1; 
     int rSize = end - middle; 
     int [] left = new int[lSize + 1]; 
     left[lSize] = Integer.MAX_VALUE; 
     int [] right = new int[rSize + 1]; 
     right[rSize] = Integer.MAX_VALUE; 
     for(int i = 0; i < lSize; i++) { 
      left[i] = data[first + i]; 
     } 

     for(int j = 0; j < rSize; j++) { 
      right[j] = data[middle + j + 1]; 
     } 

     print("Left: ", left); 
     print("Right: ", right); 

     int lIndex = 0; 
     int rIndex = 0; 

     for(int k = first; k < end; k++) { 
      if(left[lIndex] <= right[rIndex]) { 
       data[k] = left[lIndex]; 
       lIndex++; 
      } else { 
       data[k] = right[rIndex]; 
       rIndex++; 
      } 
     } 
    } 


    public void print(String message, int [] array) { 
     System.out.println(message + " : " + Arrays.toString(array)); 
    } 

    public int [] createRandomNumberArray() { 
     int [] data = new int[] {86,8,60,9,49,73,37,59,98,69} ; 
     /*int [] data = new int[SIZE]; 
     for(int i = 0; i < SIZE; i++) { 
      data[i] = RANDOM.nextInt(RANGE); 
     }*/ 
     return data; 
    } 

    public long time(long start, long end) { 
     long time = end - start; 
     System.out.println("Time taken in sorting ==> " + time); 
     return time; 
    } 

} 

Я попытался напечатать значения и отладки кода, но я не в состоянии выяснить, что здесь не так. Пожалуйста, сообщите, что может быть неправильным.

Answer 1

for(int k = first; k < **=**end; k++) { 
       if(left[lIndex] <= right[rIndex]) { 
        data[k] = left[lIndex]; 
        lIndex++; 
       } else { 
        data[k] = right[rIndex]; 
        rIndex++; 
       } 
      }