Implementing Merge Sort with Java

Question

I was trying to implement merge sort using java, but it's saying:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
    at HelloWorld.merge(HelloWorld.java:42)
    at HelloWorld.sort(HelloWorld.java:30)
    at HelloWorld.sort(HelloWorld.java:28)
    at HelloWorld.sort(HelloWorld.java:29)
    at HelloWorld.sort(HelloWorld.java:28)
    at HelloWorld.main(HelloWorld.java:10)

So I tried to copy the original array into a helper array in the merge subroutine, I think it's the length I use for helper array messed everything up, isn't "r-l+1" the length of the helper array?

If I put 100 as the length of the helper array, the code would work, but obviously it's not going to work when the size of the original array gets larger.

Please help and thanks in advance.

public class HelloWorld{

     public static void main(String []args){

         HelloWorld ms = new HelloWorld();
         int arr[] = new int[]{4,3,0,1,3,2,4,20,13,22,10};

         ms.sort(arr, 0, arr.length - 1);

         ms.printArr(arr);

     }

     void printArr(int arr[])
     {
         int n = arr.length;
         for(int i = 0; i<n; i++){
             System.out.print(" "+arr[i]);
         }
     }

     void sort(int arr[], int l, int r)
     {
         if(l<r){
             int m = (l+r)/2;
             sort(arr, l, m);
             sort(arr, m+1, r);
             merge(arr, l, m, r);

         }

     }

     void merge(int arr[], int l, int m, int r)
     {
        //find out helper array length
        int helper[] = new int[r-l+1];
         // Your code here
         for(int i=l; i<=r; i++){
             helper[i] = arr[i];
         }
         int i = l;
         int k = l;
         int j = m+1;
         while(i<=m && j<=r){
             if(helper[i]<=helper[j]){
                 arr[k]=helper[i];
                 i++;
             }else{
                 arr[k]=helper[j];
                 j++;
             }
             k++;
         }

         while(i<=m){
             arr[k]=helper[i];
             i++;
             k++;
         }
     }


}

CodingSamples · Answer 1 · 2020-01-19T02:39:45.877

You create an array with the size r - l + 1

int helper[] = new int[r-l+1];

The merge method will be executed with l = 3, m = 3, r = 4 So the array helper has a size of r - l + 1 = 2 = [0, 0]

Your for loop runs from l..r

     for(int i=l; i<=r; i++){
         helper[i] = arr[i];
     }

And you try to set the value from arr[3] to helper[3] which is not possible because helper.length = 2

That's why the ArrayIndexOutOfBoundsException occurs! You can modfiy the access to the helper index to i - l

void merge(int arr[], int l, int m, int r) {
    // find out helper array length
    int helper[] = new int[r - l + 1];
    // Your code here
    System.arraycopy(arr, l, helper, 0, helper.length);
    int i = l;
    int k = l;
    int j = m + 1;
    while (i <= m && j <= r) {
        if (helper[i - l] <= helper[j - l]) { // <---
            arr[k] = helper[i - l]; // <---
            i++;
        } else {
            arr[k] = helper[j - l]; // <---
            j++;
        }
        k++;
    }

    while (i <= m) {
        arr[k] = helper[i - l]; // <---
        i++;
        k++;
    }
}

score 0 · Accepted Answer · answered Jan 19 '20 at 02:29

If I understand the way you're attempting to implement the MERGE subroutine for your merge sort algorithm correctly, you're copying the relevant portion of the array (from index l, inclusive, to index l, inclusive) into the helper array, then modifying the original array using the data copied into the helper array.

In this case, the helper array should indeed have length r-l+1. However, taking a look at your code for copying the original array portion into the helper array, you're not offsetting your indexes in the for loop. The correct way to do it would be:

int helper[] = new int[r-l+1];

for (int i = l; i <= r; i++){
    helper[i-l] = arr[i];
}

Don't forget arrays are zero indexed!

I do however recommend moving on to more modern ways of copying arrays if you absolutely have to copy them. In this case, the most adapted in my opinion would be the system call System.arraycopy(arr, l, helper, 0, r-l+1). If you would like to read more about the different methods of copying an array (completely or partially) in Java, check this answer out.

You are right, he can copy it like this: System.arraycopy(arr, l, helper, 0, helper.length); He also need to access the correct index in the while loops at the end of the method — CodingSamples, Jan 19 '20 at 02:38

Implementing Merge Sort with Java

2 Answers2