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));
}
}