Implementing merge sort in Java: Only zeroes

Question

I'm trying to implement some sorting algorithms in Java working on int-arrays as an educational process. I currently try to wrap my head around merge sort. Yesterday I got pretty far, with a result of an array of the correct size, but only containing zeroes. Today I started new from the ground, and now I'm stuck at the same point. ^^ Here is my code:

``````public static int[] mergeSort(int[] array) {
if (array.length < 2) {
return array;
}
int left = 0;
int right = array.length;
int p = array.length / 2;
int[] lArray = Arrays.copyOfRange(array, left, p);
int[] rArray = Arrays.copyOfRange(array, p, right);
lArray = mergeSort(lArray);
rArray = mergeSort(rArray);
return merge(lArray, rArray);
}

private static int[] merge(int[] lArray, int[] rArray) {
int[] result = new int[lArray.length + rArray.length];
int idx = 0;
int rIdx = 0;
int lIdx = 0;
while (lIdx < lArray.length - 1 && rIdx < rArray.length - 1) {
if (lArray[lIdx] < rArray[rIdx]) {
result[idx] = lArray[lIdx];
lIdx++;
} else if (lArray[lIdx] >= rArray[rIdx]) {
result[idx] = rArray[rIdx];
rIdx++;
}
idx++;
}
if (lIdx < (lArray.length - 1)) {
result[idx] = lArray[lIdx + 1];
} else if (rIdx < (rArray.length - 1)) {
result[idx] = rArray[rIdx + 1];
}
return result;
}
``````

I think it's pretty OKly-styled and readable. So, all you algorith- and Java-cracks out there, what am I missing? Debugging points toward the merge method, but I can't quite pin it down, so I publish this as-is.

Show source

Answers to Implementing merge sort in Java: Only zeroes ( 3 )

1. ``````if (lIdx < (lArray.length - 1)) {
result[idx] = lArray[lIdx + 1];
} else if (rIdx < (rArray.length - 1)) {
result[idx] = rArray[rIdx + 1];
}
``````

This part is a bit strange. Why do you just copy one remaining element into your result array? You should copy all the remaining elements from either lArray or rArray into your result. Use 'while' instead of 'if'.

2. I see two issues in your `merge` method :

First of all, your while loop ignores the last element of the left and right arrays. You should change

``````while (lIdx < lArray.length - 1 && rIdx < rArray.length - 1)
``````

to

``````while (lIdx < lArray.length && rIdx < rArray.length)
``````

Second of all, After that while loop, you need two more while loops to add the tail of the left array or the tail of the right array. Instead you only add a single element.

Replace

``````if (lIdx < (lArray.length - 1)) {
result[idx] = lArray[lIdx + 1];
} else if (rIdx < (rArray.length - 1)) {
result[idx] = rArray[rIdx + 1];
}
``````

with

``````while (lIdx < lArray.length) {
result[idx++] = lArray[lIdx++];
}
while (rIdx < rArray.length) {
result[idx++] = rArray[rIdx++];
}
``````
3. Here you go

``````public class MergeSort {

public static int[] mergeSort(int[] array) {
if (array.length < 2) {
return array;
}
int left = 0;
int right = array.length;
int p = array.length / 2;
int[] lArray = Arrays.copyOfRange(array, left, p);
int[] rArray = Arrays.copyOfRange(array, p, right);
//printArray(lArray); seems ok
//printArray(rArray); seems ok
lArray = mergeSort(lArray);
rArray = mergeSort(rArray);
return merge(lArray, rArray);
}

private static int[] merge(int[] lArray, int[] rArray) {
/*System.out.println("Ive got");
printArray(lArray);
printArray(rArray); seems ok*/
int[] result = new int[lArray.length + rArray.length];
int index = 0;
int rightIndex = 0;
int leftIndex = 0;
while (leftIndex < lArray.length && rightIndex < rArray.length) { //TODO
if (lArray[leftIndex] < rArray[rightIndex]) {
result[index] = lArray[leftIndex];

leftIndex++;
index++;
//} else if (lArray[leftIndex] >= rArray[rightIndex]) { // You don't have to check it!!!
} else {
System.out.println("2 left index " + leftIndex + " index " + index);
result[index] = rArray[rightIndex];
rightIndex++;
index++;
}
}
while (leftIndex < (lArray.length)) { // TODO
result[index] = lArray[leftIndex];
index++;
leftIndex++;
}
while (rightIndex < (rArray.length)) { // TODO
result[index] = rArray[rightIndex];
index++;
rightIndex++;
}
System.out.println("Returning ");
printArray(result);
return result;
}

public static void printArray(int[] arr) {
for (int i : arr)
System.out.print(i + " ");
System.out.println();
}

public static void main(String[] args) {
int[] arr = {2, 1, 3, 4, 0, -1};
printArray(arr);
arr = mergeSort(arr);
printArray(arr);
}
}
``````

What was wrong is marked with `//TODO`