Java Mergesort sorting algorithm error

Question

I was doing the Mergesort sorting algorithm in Java for study purposes and every time it runs it gives error. I’ve already revised the logic of the algorithm, already replacing the array of integers with a ArrayList, I’ve tried to change the stopping logic but nothing.

public static void main(String[] args) {

    ArrayList<Integer> array = new ArrayList<>();

    array.add(0);
    array.add(3);
    array.add(9);
    array.add(18);
    array.add(5);
    array.add(4);
    array.add(6);
    array.add(10);

    MergeSortClass.dividir( array, 0, array.size() );

    System.out.println( array.toString() );

}

public static void dividir( ArrayList<Integer> array, int inicio, int fim ){

    if( inicio < fim ){

        int meio = ( inicio + ( fim - 1 ) ) / 2;

        dividir( array, inicio, meio );
        dividir( array, meio + 1, fim );
        intercalar( array, inicio, meio, fim );

    }

} 

 public static void intercalar( ArrayList<Integer> array, int inicio, int meio, int fim ){

    int i = inicio;
    int j = meio + 1;

    ArrayList<Integer> temp = new ArrayList<>();

    while( i < j && j < fim ){

        if( array.get(i) < array.get(j) ){

            temp.add( array.get(i) );
            i++;

        } else {

            temp.add( array.get(j) );
            j++;

        }

    }

    //No caso da árvore recursiva estar desbalanceada e um dos lados terminar de comparar, o restante do outro lado será copiado para o array temporário

    while( i < j ){

        temp.add( array.get(i) );
        i++;

    }

    while( j < fim ){

        temp.add( array.get(j) );
        j++;

    }

    for( i = 0; i < temp.size(); i++ ){

        array.set( i + inicio, temp.get(i) );

        //código abaixo só para testar
        System.out.println( array.get(i + inicio) );

    }

    System.out.println("");

}

After I run the code, at the output prompt along with the error message, I get it:

The array has been almost fully ordered.

I want to know what is the problem with my code and what is the possible solution.

Answer 1

Your program has some problems:

1. If you are working with lists, it makes no sense to call the list of array, since it is not an array but a list.

2. It’s easier to work with fim being the last item on the list (lista.size() - 1) and not the list size that would be the first item after the end of it. You even try to work with it being the first item after the end (using the ( fim - 1 ) in the method dividir), but the code gets more complicated with this.

3. His biggest problem was using the i < j in the method intercalar. What you wanted was i <= meio. With i < j you end up adding the elements of the second half of each merge twice in the resulting draft list, and then at the time of copying it back to the original list, you blow up the size of it.

4. Your method dividir should be called ordenar.

5. Prefer to use the types that are as abstract as possible, avoiding using too specific types. This way, in many places where you use ArrayList like, I could just use List.

See it here corrected:

import java.util.ArrayList;
import java.util.List;

class MergeSortClass {
    public static void main(String[] args) {
        List<Integer> lista = new ArrayList<>();
        lista.add(0);
        lista.add(3);
        lista.add(9);
        lista.add(18);
        lista.add(5);
        lista.add(4);
        lista.add(6);
        lista.add(10);
        ordenar(lista);
        System.out.println(lista.toString());
    }

    public static void ordenar(List<Integer> lista) {
        ordenar(lista, 0, lista.size() - 1);
    }

    private static void ordenar(List<Integer> lista, int inicio, int fim) {
        if (inicio >= fim) return;

        int meio = (inicio + fim) / 2;

        ordenar(lista, inicio, meio);
        ordenar(lista, meio + 1, fim);
        intercalar(lista, inicio, meio, fim);
    }

    private static void intercalar(List<Integer> lista, int inicio, int meio, int fim) {

        int i = inicio;
        int j = meio + 1;

        List<Integer> temp = new ArrayList<>(fim - inicio + 1);

        while (i <= meio && j <= fim) {
            int a = lista.get(i);
            int b = lista.get(j);
            if (a < b) {
                temp.add(a);
                i++;
            } else {
                temp.add(b);
                j++;
            }
        }

        while (i <= meio) {
            temp.add(lista.get(i));
            i++;
        }

        while (j <= fim) {
            temp.add(lista.get(j));
            j++;
        }

        for (int k = 0; k < temp.size(); k++) {
            lista.set(k + inicio, temp.get(k));
        }
    }
}

See here working on ideone.

Answer 2

The most important thing in situations like this is to know how to read the error output. It is something very simple, but in general, people ignore.

First, it should be noted that the error output is given in a stack format. This means that the first line of the error represents the last method that was called and where, effectively, the exception occurred.

In your case, the mistake happened in this section:

at java.util.ArrayList.rangeCheck(ArrayList.java:657)

rangeCheck is a class method ArrayList which checks if a given index (int) is within vector boundaries. If not, then an exception of type IndexOutOfBoundsException is launched.

Behold here an implementation of Arraylist for the OpenJDK. The code snippet below is the method rangeCheck.

/**
 * Checks if the given index is in range.  If not, throws an appropriate
 * runtime exception.  This method does *not* check if the index is
 * negative: It is always used immediately prior to an array access,
 * which throws an ArrayIndexOutOfBoundsException if index is negative.
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

Continuing the error analysis...

Note that the rangeCheck is called by the method java.util.ArrayList.set(ArrayList:448), another method of ArrayList. This, in turn, is called by the method intercalar of your class MergeSortClass. The intercalar is called by dividir and that by main.

The error, within the intercalar, happens on that line:

array.set( i + inicio, temp.get(i) );

So this call to set is generating the exception IndexOutOfBoundsException. In short: the first parameter i+inicio is outside the boundary of the vector (the internal structure of Arraylist).

Answer 3

Try MergeSortClass.dividir( array, 0, array.size()-1 ); because the Arraylist size is the amount of elements, but as it starts at 0 the last valid position is size-1.