Merge Sort Java Implementation so merge works within one array with second splitted array reversed

Question

Challenge: within a lecture on data structures and algorithms I encountered a version of merge sort which uses the merge routine in a way that the second half is being reversed from the splitting index and from there compares the first and the last element. I tried to implement in java and it always failed somehow.

Problem: The array is being sorted so that the output is [1, 2, 4, 8, 6] so the 6 is not sorted. It seems as if the recursive call is not looking at the element 6 in the last merge call.

What I tried: Shifting different indices and adding different print statements for checking. I tried to make j = r before the last for loop within merge which lead to stack overflow every time. I tried to change the way how the size of the array is being calculated, since I was not sure if the pseudo code excepts the array to start from 1 or 0. I tried to shift if(p < r-1) to if(p <= r-1) but get a stack overflow.

I looked at different implementations of java merge routine and every I found so far seems to work with two arrays. Is there a serious reason why the approach above is not working correctly or any idea how to fix this issue?

Given the following pseudo code:

void merge_sort(array& A, int p, int r) {
    if (p < r - 1) {
        int q = Floor((p + r) / 2);
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

void merge(array& A, int p, int q, int r) {
    array B(p, r - 1);
    int i, j;
    for (i = p; i < q; i++)
        B[i] = A[i];
    // Now i=q
    for (j = r; i < r; i++)
        B[--j] = A[i];
    i = p;
    j = r - 1;
    for (int k = p; k < r; k++)
        A[k] = (B[i] < B[j]) ? B[i++] : B[j--];
}

I tried to implement in java like so:

import java.util.Arrays;

public class Mergesort {

    private static int[] A = new int[]{ 4, 2, 1, 8, 6 };

    public static void main(String[] args) {
        merge_sort(0, A.length - 1);
        System.out.println(Arrays.toString(A));
    }

    public static void merge_sort(int p, int r) {
        if (p < r - 1) {
            int q = Math.floor((p + r) / 2);
            merge_sort(p, q);
            merge_sort(q + 1, r);
            merge(p, q, r);
        }
    }

    public static void merge(int p, int q, int r) {
        int[] B = new int[r - p];
        int i, j;
        for (i = p; i < q; i++)
            B[i] = A[i]
        for (j = r; i < r; i++)
            B[--j] = A[i];
        i = p;
        j = r - 1;
        for (int k = p; k < r; k++)
            A[k] = (B[i] < B[j])? B[i++] : B[j--];
    }
}

user_4593267 · Answer

There are multiple problems in your code:

the temporary array is too short: since r is the index of the last element, the size should be r - p + 1. It is much simpler to pass r as the index one past the last element of the slice to sort.
the first for loop is incorrect: you should use a different index into B and A.
the second for loop copies to B[r - 1] downwards, but it should use B[r - p] instead.
the merging loop is incorrect: you should test if i and j are still within the boundaries of the respective halves before accessing B[i] and/or B[j].
[minor] there is no need for int q = Math.floor((p + r) / 2); in java as p and r are have type int, so the division will use integer arithmetics.

Here is a modified version:

public class Mergesort {

    private static int[] A = new int[]{ 4, 2, 1, 8, 6 };

    public static void main(String[] args) {
        merge_sort(0, A.length);
        System.out.println(Arrays.toString(A));
    }

    public static void merge_sort(int p, int r) {
        if (r - p >= 2) {
            int q = p + (r - p) / 2;
            merge_sort(p, q);
            merge_sort(q, r);
            merge(p, q, r);
        }
    }

    public static void merge(int p, int q, int r) {
        int m = q - p;  // zero based index of the right half
        int n = r - p;  // length of the merged slice
        int[] B = new int[n];
        int i, j, k;
        for (i = p, j = 0; j < m; j++)
            B[j] = A[i++];
        for (i = r, j = m; j < n; j++)
            B[j] = A[--i];
        for (i = 0, j = n, k = p; k < r; k++) {
            // for stable sorting, i and j must be tested against their boundary
            // A[k] = (i < m && (j <= m || B[i] <= B[j - 1])) ? B[i++] : B[--j];
            // stability is not an issue for an array of int
            A[k] = (B[i] <= B[j - 1]) ? B[i++] : B[--j];
        }
    }
}

Reversing the second half allows for a simpler merge loop without boundary tests. Note however that there is a simpler approach that uses less memory and might be more efficient:

    public static void merge(int p, int q, int r) {
        int m = q - p;  // length of the left half
        int[] B = new int[m];
        int i, j, k;
        // only save the left half
        for (i = p, j = 0; j < m; j++)
            B[j] = A[i++];
        for (i = 0, j = q, k = p; i < m; k++) {
            A[k] = (j >= r || B[i] <= A[j]) ? B[i++] : A[j++];
        }
    }

Merge Sort Java Implementation so merge works within one array with second splitted array reversed

1 Answers