Блог

Я получаю ошибку out of bounds для моей реализации mergeSort , и я не могу понять, почему. Это точное сообщение об ошибке: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1"

Вот моя реализация mergeSort :

 public static void mergeSort(int[] arr, int n) {
    if (n < 2) {
        return;
    }
    
    int mid_index = n / 2; 
    int[] left = new int[mid_index];
    int[] right = new int[n - mid_index];
    
    for (int i = 0; i < mid_index; i  ) {
        left[i] = arr[i];
    }
    
    for (int i = mid_index; i < n; i  ) {
        right[i - mid_index] = arr[i];
    }
    
    mergeSort(left, mid_index);
    mergeSort(right, n - mid_index);
    merge(arr, left, right, mid_index, n - mid_index);
}
    
public static void merge(int[] arr, int[] left, int[] right, int left_length, int right_length) {
    int i = 0;
    int j = 0; 
    int k = 0; 
    
    while (j < left_length amp;amp; k < right_length) {
        if (left[i] < right[j]) {
            arr[k] = left[i];
            k  ;
            i  ;
        } else {
            arr[k] = right[j];
            k  ;
            j  ;
        }
    }
    
    while (j < left_length) {
        arr[k] = left[i];
        k  ;
        i  ;
    }
    
    while (i < right_length) {
        arr[k] = right[j];
        k  ;
        j  ;
    }
} 
  

Проблема была в merge методе. Вы допускаете некоторые ошибки с индексами. Я исправил их в коде ниже

 public static void merge(int[] arr, int[] left, int[] right, int left_length, int right_length){
    int i = 0;//left
    int j = 0; //right
    int k = 0; 
    
    while(i<left_length amp;amp; j < right_length){
        if(left[i] < right[j]){
            arr[k] = left[i];
            k  ;
            i  ;
        }
        else{
            arr[k] = right[j];
            k  ;
            j  ;
        }
    }
    
    while(i<left_length){
        arr[k] = left[i];
        k  ;
        i  ;
    }
    
    while(j<right_length){
        arr[k] = right[j];
        k  ;
        j  ;
        }
    } 
  

Все 3 while цикла в merge методе используют неправильные индексные переменные. Первый цикл while (j < left_length amp;amp; k < right_length) { должен быть

     while (i < left_length amp;amp; j < right_length) {
  

Второй цикл while (j < left_length) { должен быть

     while (i < left_length) {
  

Наконец, последний цикл while (i < right_length) { должен быть

     while (j < right_length) {