Thread: Converting merge method in c to java

Now, I do know several versions of merge sort in java that actually work, but for my own sake, I'd like to know why my translation of the c code below is wrong. To me it seems like the logic should be the same. Nevertheless, I have verified that the c code works and that the java code does not.


Here is the original code in c

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
 
    /* create temp arrays */
    int *L = (int *)malloc(sizeof(int)*n1);
    int *R = (int *)malloc(sizeof(int)*n2);
 
    /* Copy data to temp arrays L[] and R[] */
    for(i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for(j = 0; j <= n2; j++)
        R[j] = arr[m + 1+ j];
 
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    /* Copy the remaining elements of L[], if there are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    /* Copy the remaining elements of R[], if there are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Here is my translation into java

void merge(int arr[], int l, int m, int r)
	{
	    int i, j, k;
	    int n1 = m - l + 1;
	    int n2 =  r - m;
 
	    /* create temp arrays */
	    int []L = new int [n1];
	    int []R = new int [n2];
 
	    /* Copy data to temp arrays L[] and R[] */
	    for(i = 0; i < n1; i++)
	        L[i] = arr[l + i];
	    for(j = 0; j <= n2; j++)
	        R[j] = arr[m + 1+ j];
 
	    /* Merge the temp arrays back into arr[l..r]*/
	    i = 0;
	    j = 0;
	    k = l;
	    while (i < n1 && j < n2)
	    {
	        if (L[i] <= R[j])
	        {
	            arr[k] = L[i];
	            i++;
	        }
	        else
	        {
	            arr[k] = R[j];
	            j++;
	        }
	        k++;
	    }
 
	    /* Copy the remaining elements of L[], if there are any */
	    while (i < n1)
	    {
	        arr[k] = L[i];
	        i++;
	        k++;
	    }
 
	    /* Copy the remaining elements of R[], if there are any */
	    while (j < n2)
	    {
	        arr[k] = R[j];
	        j++;
	        k++;
	    }
	}

The error is always at the line R[j] = arr[m + 1+ j];
I thought it might be an off-by one error, so I tried putting in +1 or -1 in a few places, but still couldn't get it to work. Maybe someone here will have more success finding it.
I've heard that c doesn't translate all that well into java (I have virtually no experience with c), but I can't see how the operations used in the two above are all that different.

The error is an array index out of bound exception. I can't get much more detail than that, particularly as I don't know how to how to iterate through the eclipse debugger on my laptop (F6 doesn't work).

The merge method is supposed to merge an array, when each half of that array is sorted, into a fully sorted array.
It is supposed to take this input like this: (int [] halfSortedArray, int firstIndexInArray, int midPointOfArray,int lastIndexInarray)

An example of the algorithm in operation would be this;
int [] array = {3,4,5,6,1,2,3,4}
merge(array,0,3,7)
output: 1,2,3,3,4,4,5,6

It is usually used in conjunction with a mergeSort algorithm. Sorry I wasn't very clear about explaining it, but I'll bet you are already familiar with it. Nevertheless, for clarity, here is a java example that does the same thing that does actually work:

public static void merge(int[] a, int l, int m, int r) {
		int[] numbers = a;
		int number = a.length;
		int[] helper = new int[number];
 
		int p = l;
		int u = l;
		int v = m + 1;
 
		// Copy both parts into the helper array
		for (int i = l; i <= r; i++) {
			helper[i] = numbers[i];
		}
 
		// create empty array
		// int [] result = emptyArray(r-l+1);
 
		// Copy the smallest values from either the left or the right side back
		// to the original array
		while (p <= m && v <= r) {
			if (helper[p] <= helper[v]) {
				numbers[u] = helper[p];
				p++;
			} else {
				numbers[u] = helper[v];
				v++;
			}
			u++;
		}
		// Copy the rest of the left side of the array into the target array
		while (p <= m) {
			numbers[u] = helper[p];
			u++;
			p++;
		}
 
	}// end merge

It's not so much about getting the code to work as it is about cementing my understanding of it. The C code happens to be closer to the pseudocode in Introduction to Algorithms and other places. I wanted to convert the same logic to java to aid my understanding. Nothing more. I have a good few examples working, but they all use different logic to do it. It's funny since the actual mergeSort method is nearly always the same, but the merge method is done in so many different ways. I also want to get used to translating pseudocode. I keeping getting caught by common things like pseudocode indexing from 1 to n where a computer indexes from 0 to n-1, particularly assigning int values of 1 where it is 0 in actual code, as is the case when you compare the Introduction to Algorithms Code with the C implementation.

I've just had a proper run through the debugger. m remains 3 throughout, and, given an array of length 8, the error occurs when j =4. So, that means that given an array numbered from 0-7, it tries to assign a value from arr[8], which it can't do.

Going over this made me notice the asymmetry between the i and j for loops; one uses < and one uses <=. I changed that j for loop to <, and now I have a version that seems to work.

static void merge(int arr[], int l, int m, int r)
	{
	    int i, j, k;
	    int n1 = m - l;
	    int n2 =  r - m;
 
	    /* create temp arrays */
	    int []L = new int [n1];
	    int []R = new int [n2];
 
	    /* Copy data to temp arrays L[] and R[] */
	    for(i = 0; i < n1; i++)
	        L[i] = arr[l + i];
	    for(j = 0; j < n2; j++)
	        R[j] = arr[m + 1+ j];
 
	    /* Merge the temp arrays back into arr[l..r]*/
	    i = 0;
	    j = 0;
	    k = l;
	    while (i < n1 && j < n2)
	    {
	        if (L[i] <= R[j])
	        {
	            arr[k] = L[i];
	            i++;
	        }
	        else
	        {
	            arr[k] = R[j];
	            j++;
	        }
	        k++;
	    }
 
	    /* Copy the remaining elements of L[], if there are any */
	    while (i < n1)
	    {
	        arr[k] = L[i];
	        i++;
	        k++;
	    }
 
	    /* Copy the remaining elements of R[], if there are any */
	    while (j < n2)
	    {
	        arr[k] = R[j];
	        j++;
	        k++;
	    }
	}

I still have to test it thoroughly, but looks like it was an off by one error. Why am I not surprised? It's always an off by one error!