## Monday, September 15, 2014

### Merge Sort Implementation In Java

This program implements Merge Sort Algorithm.

Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm. Have a quick read here if you like.

Code:

```import java.util.Arrays;

public class MergeSort {

public static void mergeSort(int[] orig){
int temp[] = new int[orig.length];
mergeSorter(0, orig.length-1, orig, temp);
}

private static void mergeSorter(int beg, int end, int[] orig, int[] temp) {
if (beg == end) {
return;
}
mergeSorter(beg, (beg + end) / 2, orig, temp);
mergeSorter((beg + end) / 2 + 1, end, orig, temp);
merge(beg, end, orig, temp);
System.arraycopy(temp, beg, orig, beg, (end-beg+1));
}

private static void merge(int beg, int end, int[] orig, int[] temp){
int s1 = beg;           //first half starting position
int e1 = (beg+end)/2;   //first half ends here
int s2 = (beg+end)/2+1; //second half starts here
int e2 = end;

int i = beg, l = s1, r = s2;
while(l<=e1 && r<=e2){
if (orig[l] >= orig[r]) {
temp[i] = orig[r];
r++;
} else if (orig[l] < orig[r]) {
temp[i] = orig[l];
l++;
}
i++;
}

if (l == e1+1) {
System.arraycopy(orig, r, temp, i, e2-r+1);
} else if (r == e2+1) {
System.arraycopy(orig, l, temp, i, e1-l+1);
}
}

public static void main(String[] args) {
int[] input = new int[]{5, 6, 3, 2, 2, 9, 9, 0};    //test array
MergeSort.mergeSort(input);
System.out.print(Arrays.toString(input));
}
}```

Output:
[0, 2, 2, 3, 5, 6, 9, 9]

as expected.