Merge sort implementation in java is copying a value into another index instead of swapping

Question

I am implementing a merge sort algorithm. But, my code, for some reason, keeps copying one of the values and puts it back in to my array twice instead of doing a swap. I was wondering if someone can take a look and let me know where this might be happening and how I can fix it.

public static void mergeSort(int[] a, int p, int r) {
    int q;
    if (p < r) {
        q = (p + r) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q + 1, r);
        merge(a, p, q, r);
    }
}

private static void merge(int[] a, int p, int q, int r) {
    int s1 = q - p + 1;
    int s2 = r - q;

    int B[] = new int[s1];
    int C[] = new int[s2];

    for (int i = 0; i < s1; i++) {
        B[i] = a[p + i];
    }
    for (int j = 0; j < s2; j++) {
        C[j] = a[q + 1 + j];
    }
    int i = 0;
    int j = 0;
    int k = p;
    while (i < s1 && j < s2) {
        if (B[i] <= C[j]) {
            a[k] = B[i];
            i++;
        } else {
            a[k] = C[j];
            j++;
        }
        k++;
    }

    while (i < s1) {
        a[k] = B[i];
        i++;
        k++;
    }
    while (j < s2) {
        a[k] = B[j];
        j++;
        k++;
    }
}

My current input for one instance is: { 1317884528, 359761860, -513283737, 369485540, 564749187 }

The output is: { -513283737, 359761860, 369485540, 369485540, 1317884528 }

I can tell that it is sorting somewhat properly, but it is having problems with swapping.

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) — Andreas, May 10 '19 at 17:16
@PaulAnthonyMorillo: you can accept the answer by clicking on the grey checkmark below its score. — chqrlie, Jul 15 '19 at 13:13

chqrlie · Answer 1 · 2019-05-13T17:12:56.887

The last loop is incorrect: it should copy the remaining elements from C, not from B:

while (j < s2) {
    a[k] = C[j];
    j++;
    k++;
}

Note that the code would be simpler and less prone to off by one errors if the r argument to mergeSort was the first excluded index instead of the last included index:

/* sort an array of integers `a[]`. call as `mergeSort(a, 0, a.length)` */
public static void mergeSort(int[] a, int p, int r) {
    if (r - p > 1) {
        int q = p + (r - p + 1) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q, r);
        merge(a, p, q, r);
    }
}

private static void merge(int[] a, int p, int q, int r) {
    int s1 = q - p;
    int s2 = r - q;

    /* save the left part, the right part does not need saving */
    int B[] = new int[s1];
    for (int i = 0; i < s1; i++) {
        B[i] = a[p + i];
    }
    int i = 0;
    int j = q;
    int k = p;
    while (i < s1 && j < r) {
        if (B[i] <= a[j]) {
            a[k++] = B[i++];
        } else {
            a[k++] = a[j++];
        }
    }
    while (i < s1) {
        a[k++] = B[i++];
    }
}

Merge sort implementation in java is copying a value into another index instead of swapping

1 Answers1