Search code examples
javaalgorithmsortingdebuggingmergesort

Mergesort implementation not correct


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++];
        }
    }

Solution

  • 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]