java - Mergesort implementation not correct -
i have been trying write basic top down mergesort, array not sorted after code has finished executing. have tried debugging recursion makes tough pinpoint. have tried comparing code other examples of mergesort, i've had no luck finding 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 = lo;i <= hi;i++) aux[i] = arr[i]; int x = lo; int y = mid + 1; for(int = lo; <= 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]
Comments
Post a Comment