merge sort output is not fully sorted

Question

I am trying to implement merge sort algorithm from "Introduction to algorithm" book using Java, but when I execute the code, I have output semi-sorted:

input  = 2,4,5,1,2,3,6,7
output = 2,2,3,4,5,1,2,7 

public class Main {

    public static void main(String[] args) {
        int A[] = {
            2, 4, 5, 1, 2, 3, 6, 7
        };

        int B[] = new Main().mergeSort(A, 0, A.length);
        for (int i = 0; i < B.length; i++) {
            System.out.println(B[i]);
        }
    }

    void merge(int A[], int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;
        System.out.println("-n1: " + n1 + " n2: " + n2);
        int L[] = new int[n1];
        int R[] = new int[n2];


        for (int i = 0; i < n1; i++) {

            L[i] = A[p + i];
            System.out.println("L--|" + L[i]);
        }
        for (int j = 0; j < n2; j++) {
            R[j] = A[q + j];
            System.out.println("R--|" + R[j]);
        }

        int i = 0;
        int j = 0;

        for (int k = p; k < r; k++) {
            if (L[i] <= R[j]) {

                A[k] = L[i];
                System.out.println("A--|" + A[k] + " i: " + i);
                i = i + 1;
            } else {

                A[k] = R[j];
                System.out.println("A--|" + A[k] + " j: " + j);
                j = j + 1;
            }

            if (i == L.length || j == R.length) break;
        }
    }

    int[] mergeSort(int A[], int p, int r) {
        if (p < r) {
            int q = (int) Math.floor((p + r) / 2);
            mergeSort(A, p, q);
            mergeSort(A, q + 1, r);
            System.out.println("q: " + q + " p: " + p + " r:" + r);
            merge(A, p, q, r);
        }
        return A;
    }
}

If somebody can help me in this code, I would be grateful. I know there are plenty of ready made implementation in Java, and in this form, I just wanna know what is wrong with my code.

Answer 1

Thanks for your suggestions, i managed to make it work as shown below.

void merge(int A[], int low, int mid, int high) {
    int leftN = mid - low + 1;
    int rightN = high - mid;
    System.out.println("n1: " + leftN + " n2: " + rightN + " q: " + mid + " p: " + low + " r:" + high);
    int L[] = new int[leftN + 1];
    int R[] = new int[rightN + 1];

    L[leftN] = Integer.MAX_VALUE;
    R[rightN] = Integer.MAX_VALUE;

    for (int i = 0; i < leftN; i++) {

        L[i] = A[low + i - 1];
        System.out.println("L--|" + L[i]);
    }
    for (int j = 0; j < rightN; j++) {
        R[j] = A[mid + j];
        System.out.println("R--|" + R[j]);
    }

    int i = 0;
    int j = 0;

    for (int k = low - 1; k < high; k++) {

        if (L[i] <= R[j]) {

            A[k] = L[i];
            System.out.println("A--|" + A[k] + " i: " + i + " R[i] " + L[i]);
            i++;
        } else {

            A[k] = R[j];
            System.out.println("A--|" + A[k] + " j: " + j + " R[j] " + R[j]);
            j++;
        }
    }

}

int[] mergeSort(int A[], int low, int high) {
    if (low < high) {

        int mid = (low + high) / 2;
        System.out.println("q: " + mid + " p: " + low + " r:" + high);
        mergeSort(A, low, mid);
        mergeSort(A, mid + 1, high);
        merge(A, low, mid, high);

    }

    return A;
}

Answer 2

Don't use printf() to debug. It can help you see what's going on, but put breakpoints and use a debugger. That'll clear it up for you, but here are some suggestions you can immediately do:

1. Don't name your variables p,q,r, etc. Rename them "high", "low", "middle". Rename "n1" as leftLen, etc. That greatly improves readability for other programmers and helps you understand what's going on.

2. Think about what your programs are doing. Your "mergeSort()" is totally standard so the issue must lie within your merge program. Instead of running mergeSort, run merge by itself and see what's happening. Try to understand how your merge program is working, and compare it what you THINK it's doing.

3. Specifically, consider your L[] and R[]. Can they ever be empty? If so, what happens?

4. What about duplicates? Can you ever store the same number in both the left and right array? Does that affect your code?

5. Is there a better way to store the range of numbers?

Best of luck!