Merge Sort. Error-- Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2

Question

Good day, everyone! I have here a program that sorts 50,000 words from a file using merge sort. I followed Thomas Cormen's pseudocode in his Introduction to Algorithms and it seems right when I'm "debuuging" it by hand manually. However, when I run the program it says Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2 . Yes, I think it is due to the large NO_OF_WORDS (ie, 50,000) but even though I decreased it to 10, still, it shows the same error.

import java.io.*;
import java.util.*;

public class SortingAnalysis {

    public static void merge(String[] A, int p, int q, int r) {
        int n1 = q-p+1;
        int n2 = r-q;
        String[] L = new String[n1+1];
        String[] R = new String[n2+1];
        for (int i=1; i<n1; i++) {
            L[i] = A[p+i-1];
        }
        for (int j=1; j<n2; j++) {
            R[j] = A[q+j];
        }
        L[n1+1] = "zzzzz"; //for infinity because if I use Math.floor, it will return a double
        R[n2+1] = "zzzzz";
        int i=1;
        int j=1;
        for (int k=p; k<=r; k++) {
            int comparison = L[i].compareTo(R[j]);
            if (comparison <= 0){
                A[k] = L[i];
                i++;
            }
            else {
                A[k] = R[j];
                j++;
            }

        }

    }

    public static void mergeSort (String[] A, int p, int r) {
        if (p<r) {
            int q = (p+r)/2;
            mergeSort(A, p, q);
            mergeSort(A, q+1, r);
            merge(A, p, q, r);
        }
    }

    public static void main(String[] args) {
        final int NO_OF_WORDS = 50000;
        try {
            Scanner file = new Scanner(new File(args[0]));
            String[] words = new String[NO_OF_WORDS];

            int i = 0;
            while(file.hasNext() && i < NO_OF_WORDS) {
                words[i] = file.next();
                i++;
            }
            long start = System.currentTimeMillis();

            mergeSort(words, 0, words.length-1);

            long end = System.currentTimeMillis();
            System.out.println("Sorted Words: ");
            for(int j = 0; j < words.length; j++) {
                System.out.println(words[j]);
            }   
            System.out.print("Running time: " + (end - start) + "ms");

        }
        catch(SecurityException securityException) {
            System.err.println("Error");
            System.exit(1);
        }
        catch(FileNotFoundException fileNotFoundException) {
            System.err.println("Error");
            System.exit(1);
        } 
    } 
}

I think it's because of the declaration of String[] L and R. Or not. Please help me what's the problem. Thank you very much!

EDIT
Cormen's Pseudocode

MERGE(A, p, q, r )
n1 ← q − p + 1
n2 ←r − q
create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
for i ← 1 to n1
     do L[i ] ← A[p + i − 1]
for j ← 1 to n2
     do R[ j ] ← A[q + j ]
L[n1 + 1]←∞
R[n2 + 1]←∞
i ← 1
j ← 1
for k ← p to r
     do if L[i ] ≤ R[ j ]
        then A[k] ← L[i ]
             i ←i + 1
        else A[k] ← R[ j ]
             j ← j + 1

What's the line where the error occurs? Tips: final static int NO_OF_WORDS = 50000; , int i = -1; while(++i < NO_OF_WORDS) , int length = words.length; for(int j = -1; ++j < length;) — Flavio Cysne
– Flavio Cysne, Commented Jul 10, 2012 at 14:01
Line where L[n1+1] = "zzzzz";, merge(A, p, q, r);, mergeSort(A, p, q); and mergeSort(words, 0, words.length-1);. With all due respect @FlavioCysne, I think the problem is not in the main. Actually, it also performs quicksort and insertion sort (which work fine) but I just deleted those parts for you not to be confused. :) Thank you! — First Lady
– First Lady, Commented Jul 10, 2012 at 14:08
Arrays.sort there's your sorting algorithm :) Remember that java arrays are 0-indexed, array[array.length] = XX won't ever work. — Jacob is on Codidact
– Jacob is on Codidact, Commented Jul 10, 2012 at 14:46

alain.janinm · Accepted Answer · 2012-07-10 16:02:59Z

I don't know what is your pseudocode but your implementation seems wrong. I've look at the wikipedia merge sort and it's quite different.

So I will not give you the full working algorithm here. I'll just give you the solution to resolve your problem of indexOutOfBounds but you still have to work more on your implementation.

In Java when you do that :

String[] L = new String[5];

You declare an array of string that can contains 5 strings within.

The access to those strings is made this way : L[anIndex].

The first element is at index 0.

So if you have an array of size 5 then the last element is at index 4 (because we start from 0).

In your code you do this :

String[] L = new String[n1+1];
String[] R = new String[n2+1];

then :

L[n1+1] = "zzzzz";
R[n2+1] = "zzzzz";

So here you always try to access a string at an index that doesn't exist. The last element in each array is respectively n1 and n2 (because arrays size are n1+1 and n2+1 ).

I hope you'll understand better how array works in Java with this explanation. Now you have to improve your implementation because it's still not working. Maybe give us the pseudocode you use if you don't understand it well.

EDIT :

Ok I made some correction.

Here is the working algorithm. I've had to change several index to fit Java "based-0 arrays", take a look :

import java.io.*;
import java.util.*;

public class SortingAnalysis {

    public static void merge(String[] A, int p, int q, int r) {
        int n1 = q-p+1;
        int n2 = r-q;
        if(A[p]==null || A[q]==null)return;
        String[] L = new String[n1+1];
        String[] R = new String[n2+1];
        for (int i=0; i<n1; i++) {
            L[i] = A[p+i];
        }
        for (int j=0; j<n2; j++) {
            R[j] = A[q+j +1];
        }
        L[n1] = "zzzzz"; //for infinity because if I use Math.floor, it will return a double
        R[n2] = "zzzzz";
        int i=0;
        int j=0;
        for (int k=p; k<=r; k++) {
            int comparison = L[i].compareTo(R[j]);
            if (comparison <= 0){
                A[k] = L[i];
                i++;
            }
            else {
                A[k] = R[j];
                j++;
            }

        }

    }

    public static void mergeSort (String[] A, int p, int r) {
        if (p<r) {
            int q = (p+r)/2;
            mergeSort(A, p, q);
            mergeSort(A, q+1, r);
            merge(A, p, q, r);
        }
    }

    public static void main(String[] args) {
        final int NO_OF_WORDS = 50000;
        try {
            Scanner file = new Scanner("bla blya blay byla ybla");
            ArrayList<String> words = new ArrayList<String>();

            while(file.hasNext() && words.size() < NO_OF_WORDS) {
                words.add(file.next());
            }
            String [] wordsArray = new String[words.size()];
            words.toArray(wordsArray);
            long start = System.currentTimeMillis();

            mergeSort(wordsArray, 0, wordsArray.length-1);

            long end = System.currentTimeMillis();
            System.out.println("Sorted Words: ");
            for(int j = 0; j < wordsArray.length; j++) {
                System.out.println(wordsArray[j]);
            }   
            System.out.print("Running time: " + (end - start) + "ms");

        }
        catch(SecurityException securityException) {
            System.err.println("Error");
            System.exit(1);
        }

    }
}

Note that I've change your Main, now I use an arrayList to avoid null value, if your text contains less words than the original array size. With your solution if you don't fill the 50000 words you get null in the array and then nullPointerException in the merge algo.

Hello, thank you! It just occurred to me that Cormen's pseudocode starts at 1, not 0. When I removed the +1 form L[n+1] and R, there is still the same error. I now included Cormen's pseudocode for merge.
Wow, thank you so much, alain.janinm!! You not just helped me finish the code but you enlightened me as well for you introduced me new techniques. I'm so thankful you happen to find my question. More power!
@FirstLady You're welcome! Glad my answer help you learn something ;)

Keppil · Accepted Answer · 2012-07-10 14:07:14Z

1

There is a big problem with your merge() method:

String[] L = new String[n1+1];
String[] R = new String[n2+1];

will not play well with

L[n1+1] = "zzzzz"; //for infinity because if I use Math.floor, it will return a double
R[n2+1] = "zzzzz";

You will get an ArrayIndexOutOfBoundsException here regardless of the values of n1 and n2 since arrays are 0-based in Java.

answered Jul 10, 2012 at 14:07

Keppil

46.3k9 gold badges101 silver badges121 bronze badges

3 Comments

First Lady Over a year ago

Thanks, Keppil! What should I do with my declaration for infinity instead? I tried Math.floor but I'm just having problems passing the parametes because it returns a double.

Keppil Over a year ago

From what I understand this is just a marker to let you know that the list is exhausted. In that case, null should work fine.

First Lady Over a year ago

Thanks. I set L[..] and R[..] to null but the still, array index out of bounds.

Collectives™ on Stack Overflow

Merge Sort. Error-- Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2

2 Answers 2

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related