Merge Sort in Java/C of an Integer Array

Conceptually, a merge sort works as follows [From wiki]

1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
2. Divide the unsorted list into two sublists of about half the size.
3. Sort each sublist recursively by re-applying the merge sort.
4. Merge the two sublists back into one sorted list.

Merge sort incorporates two main ideas to improve its runtime:

1. A small list will take fewer steps to sort than a large list.
2. Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they're already sorted .

public class CodeTest {
static int counter =0;

public static void main(String[] args) {
int input[] = {94,34,53,21,100,102, 21, 53,45, 456, 3, 32,1,5,4};

System.out.print("Before Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

mergeSort(input, 0, input.length-1);

System.out.print("\nAfter Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

System.out.println("\nmergerSort() Function is called " + counter + " times");
}

public static void mergeSort(int input[], int left, int right) {
int center;

counter++;

if (left < right) {
center = (left + right)/2;
mergeSort(input, left, center);
mergeSort(input, center+1, right);

merge(input, left, right, center);
}
}

public static void merge(int input[], int left, int right, int center) {
int i = left, j = center + 1, idx = left;
int[] temp = new int[input.length];

while( i<=center && j<=right) {
if(input[i] < input[j])
temp[idx++] = input[i++];
else if (input[i] > input[j]) 
temp[idx++] = input[j++];
else {
temp[idx++] = input[i++];
temp[idx++] = input[j++];
}

if(i > center ) 
while(j<=right)
temp[idx++] = input[j++];
else if (j > right)
while(i<=center)
temp[idx++] = input[i++];
}

for (i = left; i <=right; i++)
input[i] = temp[i];
}
}

Posted in C, Java, Merge Sort, mergesort, Programming, sorting algorithm