0

I practice coding about Merge Sort algorithm in java. At first it looks good, but there are a couple of issues in the "if" condition.

In my code, firstly I iterate the original array to merge two different subarrays. So I make a condition that as long as the "i" is less than or greater than or equal to mid, Arr[low + i], which of Arr is the original array, is assigned to arr_left[i]. When I run the code, the errors of index out of bounds occurs.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 8 out of bounds for length 8
    at baseproj/basetest.MergeSort.merge(MergeSort.java:24)
    at baseproj/basetest.MergeSort.main(MergeSort.java:12)

I am just a beginner in java. So, I would really appreciate it if anyone senior could explain why it is the error and how I can solve it.

Following is my code. However, this is not the absolute complete code, it is just a block of code.

package sorting_algorithm;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 10, 56, 27, 18, 32};
        int low = 0;
        int high = arr.length - 1;
        int mid = high / 2;
        merge(arr, low, mid, high);
    }

    public static void merge(int[] Arr, int low, int mid, int high) {
        int[] arr_left = new int[mid - low + 1];
        int[] arr_right = new int[high - mid];
        for (int i = 0; i < Arr.length; i++) {
            if (i <= mid) {
                arr_left[i] = Arr[low + i];
            }
            else {
                arr_right[i] = Arr[mid + 1 + i];
            }
        }
        System.out.println(Arrays.toString(arr_left));
        System.out.println(Arrays.toString(arr_right));
    }
}

As the nature of merge sort algorithm, I am trying to divide the original array into two different subarrays by letting the original array iterates and assigns to both left array and right array correctly using if condition.

Abra
  • 19,142
  • 7
  • 29
  • 41
Phone Myat Thu
  • 1
  • 1
  • The error could not be more apparent. You are trying to access 8th index in an array of size 8. probably your logic is not handling the edge case of when it should move next. All it needs is a proper debugging. – Kraken Aug 26 '23 at 07:44
  • Your calculation of the indexes for `arr_right` and `Arr` is wrong in this line of your code: `arr_right[i] = Arr[mid + 1 + i];`. Try this instead: `arr_right[i - mid - 1] = Arr[i];`. Step through your code with a debugger to understand why your code does not work. – Abra Aug 26 '23 at 07:49
  • What is `line 24` of your code? but `Arr[mid + 1 + i]` looks suspicious ... – derpirscher Aug 26 '23 at 07:49

1 Answers1

-1

You can debug your code with a debug tool, e.g., this online one https://www.onlinegdb.com/online_java_debugger, then you will see the exception below, which means "arr_right[i] = Arr[mid + 1 + i];" raises the exception because of mid + 1 + i equals 8 here. This happens when i is 4, and the state variables are: low:0, mid:3, high:7.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 8 out of bounds for length 8 at Main.merge(Main.java:32) at Main.main(Main.java:18)

zjg.robin
  • 95
  • 1
  • 5