Implementation of mergesort / merge-method

Question

I tried to implement the mergesort algorithm. The merge method might be wrong. Here is my code so far:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    mergesort(list, 0, list.size() - 1);
}   

private static <T extends Comparable<? super T>> void mergesort(List<T> list, int i, int j) {
    if (j - i < 1)
        return;
    int mid = (i + j) / 2;
    mergesort(list, i, mid);
    mergesort(list, mid + 1, j);
    merge(list, i, mid, j);
}

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int half = q - p + 1;
    int otherhalf = r - q;

    List<T> left = new ArrayList<T>();
    List<T> right = new ArrayList<T>();

    for (int i = 0; i < half; i++) {
        left.add(i, a.get(p + i));
    }
    for (int i = 0; i < otherhalf; i++) {
        right.add(i, a.get(q + i + 1));
    }

    int leftindex, rightindex, resultindex;
    leftindex = rightindex = resultindex = 0;

    while (leftindex < left.size() || rightindex < right.size()) {

        if (leftindex < left.size() && rightindex < right.size()) {

            if (left.get(leftindex).compareTo(right.get(rightindex)) < 0) {
                a.set(resultindex, left.get(leftindex));
                resultindex++;
                leftindex++;
            } else {
                a.set(resultindex, right.get(rightindex));
                resultindex++;
                rightindex++;
            }
        } else if (leftindex < left.size()) {
            a.set(resultindex, left.get(leftindex));
            resultindex++;
            leftindex++;
        } else if (rightindex < right.size()) {
            a.set(resultindex, right.get(rightindex));
            resultindex++;
            rightindex++;
        }   
    }
}

I tested it. As an input I choose [5, 6, 1, 4].

The output was: [1, 1, 4, 4]:

It seems that I did not get to the position 5 and 6 in merge method. So I think, I have to increment something, but I do not know where? Can anybody help me ?

Answer 1

The problem is resultindex is initialized to 0 instead of p.

Here are some other notes:

• it would be simpler to use the index of the first excluded value for the right limit instead of that of the last element. It avoid + 1 adjustments that may cause off by one errors.
• the comparison should be if (left.get(leftindex).compareTo(right.get(rightindex)) <= 0) instead of < to ensure stable sort.
• the test else if (rightindex < right.size()) is redundant.
• you can reduce the number of tests by writing 3 loops: one for as long as both halfs have members, then one to copy the rest of the left half, finally one to copy the rest of the right half.
• your variable names are not idiomatic in java.

Here is a corrected version:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    mergesort(list, 0, list.size());
}   

private static <T extends Comparable<? super T>> void mergesort(List<T> list, int i, int j) {
    if (j - i < 2)
        return;
    int mid = (i + j) / 2;
    mergesort(list, i, mid);
    mergesort(list, mid, j);
    merge(list, i, mid, j);
}

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int leftLen = q - p;
    int rightLen = r - q;

    List<T> left = new ArrayList<T>();
    List<T> right = new ArrayList<T>();

    for (int i = 0; i < leftLen; i++) {
        left.add(i, a.get(p + i));
    }
    for (int i = 0; i < rightLen; i++) {
        right.add(i, a.get(q + i));
    }

    int leftIndex = 0;
    int rightIndex = 0;
    int resultIndex = p;

    while (leftIndex < leftLen && rightIndex < rightLen) {
        if (left.get(leftIndex).compareTo(right.get(rightIndex)) <= 0) {
            a.set(resultIndex, left.get(leftIndex));
            resultIndex++;
            leftIndex++;
        } else {
            a.set(resultIndex, right.get(rightIndex));
            resultIndex++;
            rightIndex++;
        }
    }
    while (leftIndex < leftLen) {
        a.set(resultIndex, left.get(leftIndex));
        resultIndex++;
        leftIndex++;
    }
    while (rightIndex < rightLen) {
        a.set(resultIndex, right.get(rightIndex));
        resultIndex++;
        rightIndex++;
    }   
}

Furthermore, there is no need to save the right half because its elements never get overwritten before they are copied. Indeed copying the rest of the right half is useless because these elements are already in place.

Here is a simplified version:

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int half = q - p;
    List<T> left = new ArrayList<T>();

    for (int i = 0; i < half; i++) {
        left.add(i, a.get(p + i));
    }

    int leftIndex = 0;
    int rightIndex = q;
    int resultIndex = p;

    while (leftIndex < half && rightIndex < r) {
        if (left.get(leftIndex).compareTo(a.get(rightIndex)) <= 0) {
            a.set(resultIndex, left.get(leftIndex));
            resultIndex++;
            leftIndex++;
        } else {
            a.set(resultIndex, a.get(rightIndex));
            resultIndex++;
            rightIndex++;
        }
    }
    while (leftIndex < half) {
        a.set(resultIndex, left.get(leftIndex));
        resultIndex++;
        leftIndex++;
    }
}

Further simplifying the code:

• a dynamic List is not required for the left array,
• some local variables can be omitted as well
• a combined test makes the last loop useless.

Here is the simplified but potentially less readable code:

private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
    int i, half = q - p;
    T[] left = new T[half];

    for (i = 0; i < half; i++)
        left[i] = a.get(p + i);

    for (i = 0; i < half; ) {
        if (q == r || left[i].compareTo(a.get(q)) <= 0)
            a.set(p++, left[i++]);
        else
            a.set(p++, a.get(q++));
    }
}