Merge Sort implementation in Java

Question

Can you check my merge sort implementation? From all of my testing it seems like it works, but I just wanted to make sure I am doing it as good as possible, and it couldn't be optimized any further.

private static void merge(int[] c,int[] a, int[] b){
 int i = 0;//index for a
 int j = 0;//index for b
 for(int k = 0; k < c.length; k++){
 //check a[] edge case
 if(i >= a.length){
 c[k] = b[j];
 j++;
 }else if(j >= b.length){
 c[k] = a[i];
 i++;
 }else if(a[i] < b[j]) {
 c[k] = a[i];
 i++; 
 } else {
 c[k] = b[j];
 j++;
 }
 }
}
public static void mergeSort(int[] A){
 if(A.length > 1){
 int pivot = A.length / 2;
 int[] left = Arrays.copyOfRange(A, 0, pivot);
 int[] right = Arrays.copyOfRange(A, pivot,A.length);
 mergeSort(left);
 mergeSort(right);
 merge(A,left,right);
 }
}

Answer 1

Mostly LGTM, with the following objections.

• Names. Avoid which require a comment to be understood. I'd have no problem with int ax; because it clearly conveys the goal of being an index of a.

• Conditionals.

• You can statically prove that i > a.length is not possible. If by any chance it happens, it means that something really weird is going on. A good cause to raise an exception. Bottomline is, separate a == test from > one.

• Once one of the ranges is exhausted, there's no need to test it again and again. Normally one would break a main loop and copy the remaining data separately

along the lines of:

while (A has data) and (B has data)
 calculate what to copy
 copy it to C
while (A has data)
 copy A to C
while (B has data)
 copy B to C

• Types. The methods cry to be generic. If you didn't cover generics yet, disregard the objection.

Answer 2

This is new implementation. It is a little bit longer, but I think that it is easier to read.

private static <T extends Comparable<T>>void merge(T[] sorted,T[] left,T[] right){
 int leftIndex = 0;
 int rightIndex = 0;
 int sortedIndex = 0;
 //while left and right both have data
 while(leftIndex < left.length && rightIndex < right.length){
 if(left[leftIndex].compareTo(right[rightIndex]) < 0) {
 sorted[sortedIndex] = left[leftIndex];
 leftIndex++; 
 } else {
 sorted[sortedIndex] = right[rightIndex];
 rightIndex++;
 }
 sortedIndex++;
 }
 //while left has data
 while(leftIndex < left.length){
 sorted[sortedIndex] = left[leftIndex];
 leftIndex++;
 sortedIndex++;
 }
 //while right has data
 while(rightIndex < right.length){
 sorted[sortedIndex] = right[rightIndex];
 rightIndex++;
 sortedIndex++;
 }
}
public static <T extends Comparable<T>> void mergeSort(T[] A){
 if(A.length > 1){
 int pivot = A.length / 2;
 T[] left = Arrays.copyOfRange(A, 0, pivot);
 T[] right = Arrays.copyOfRange(A, pivot,A.length);
 mergeSort(left);
 mergeSort(right);
 merge(A,left,right);
 }
}

• JaDogg: You can also post follow up questions. See the help center.

Answer 3

An updated version (a follow-up question would look better indeed) is very close to be very good. However notice that last two loops are identical. It is a good indication that they represent an important algorithm which shall be recognized and factored out. In this case, it is copy().

Another deficiency worth mentioning is that the code is restricted to arrays. In reality the only thing merge needs is an ability to access next element. Sounds like merge arguments want to be iterators.