Mergesort with an odd arrayList size mixes the numbers up slightly

Viewed 39

Recently I fixed up my mergesort function, and it works perfectly with evenly sized arraylists. However, with odd sized arraylists, it slightly mixes up the results. This is an example:

org.opentest4j.AssertionFailedError: expected: <[2, 3, 4, 5, 6, 7, 8]> but was: <[2, 4, 5, 6, 7, 3, 8]>

Here is the code:

protected static <T extends Comparable<? super T>> void mergesort(ArrayList<T> list) {
    ArrayList<T> tempList = generateArrayList(list.size());
    mergesort(list, tempList, 0, list.size() - 1);
}

//helper method for merge sort driver
public static <T extends Comparable<? super T>> void mergesort(ArrayList<T> list, ArrayList<T> tempList, int left, int right) {
    if ((right - left) > insertThreshold) {
        int mid = (left + right) / 2;
        mergesort(list, tempList, left, mid);
        mergesort(list, tempList, mid + 1, right);
        merge(list, tempList, left, mid + 1, right);
    } else if ((right - left) <= insertThreshold) {
        insertionSort(list, right, left);
    }
}

public static <T extends Comparable<? super T>> void merge(ArrayList<T> list, ArrayList<T> tempList, int left, int right, int rEnd) {
    int i = left;//k

    int lNew = left;//i

    int rNew = right;//j
    int lEnd = right - 1;

    while (lNew <= lEnd && rNew <= rEnd) {
        if (list.get(lNew).compareTo(list.get(rNew)) <= 0) {
            tempList.set(i, list.get(lNew));
            i++;
            lNew++;
        } else {
            tempList.set(i, list.get(rNew));
            i++;
            rNew++;
        }
    }
    while (lNew <= lEnd) {
        tempList.set(i, list.get(lNew));
        i++;
        lNew++;
    }

    while (rNew <= rEnd) {
        tempList.set(i, list.get(rNew));
        i++;
        rNew++;
    }
    for (int j = left; j <= rEnd; j++) {
        list.set(j, tempList.get(j));
    }
}
0 Answers
Related