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

Code :

/* 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

Code :

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.

Re: Converting merge method in c to java

Quote:

The error is always at the line R[j] = arr[m + 1+ j];

Can you explain what the "error" is?

Quote:

merge the two haves arr[l..m] and arr[m+1..r] of array arr[]

Can you explain what the code is supposed to do? Perhaps by giving an example of the input and the output (or the before and after)

Re: Converting merge method in c to java

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:

Code :

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

Re: Converting merge method in c to java

What is the value of the index that is out of bounds? It is usually shown in the error message.

What are the values of m and j when the error happens?

Quote:

here is a java example that does the same thing that does actually work:

If you have a working program, what needs to be done now?

Re: Converting merge method in c to java

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.

Code :

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! :mad:

Re: Converting merge method in c to java