I have been trying to write a basic top down mergesort, but the array is not fully sorted after the code has finished executing. I have tried debugging it but all the recursion makes it tough to pinpoint. I have also tried comparing my code to other examples of mergesort, but I've had no luck finding any differences
private void mergeSort(int[] arr) {
int[] aux = new int[arr.length];
sort(arr, aux, 0, arr.length - 1);
}
private void sort(int[] arr, int[] aux, int lo, int hi) {
if(hi <= lo)
return;
int mid = lo + ((hi - lo) / 2);
sort(arr, aux, lo, mid);
sort(arr, aux, mid + 1, hi);
merge(arr, aux, lo, mid, hi);
}
private void merge(int[] arr, int[] aux, int lo, int mid, int hi) {
for(int i = lo;i <= hi;i++)
aux[i] = arr[i];
int x = lo;
int y = mid + 1;
for(int i = lo; i <= hi; i++){
if(x > mid) arr[i] = aux[y++];
else if(y > hi) arr[i] = aux[x++];
else if(aux[y] < aux[i]) arr[i] = aux[y++];
else arr[i] = aux[x++];
}
}
Change
else if(aux[y] < aux[i]) arr[i] = aux[y++];
to
else if(aux[y] < aux[x]) arr[i] = aux[y++];
note aux[x]