Tuesday, August 26, 2014

Java Merge Sort Source Code

I was not able to find a good implementation of merge sort in java as most of the implementations online didn't use comparable and have flags for sorting direction, so I decided to write one of my own.

import java.util.Arrays;


public class MergeSort {

public static void main(String[] args) {
Integer[] a = new Integer[] {3,2,1,4,2,7,1,3,4,5,6,8,9,6,7,8};
sort(a,false);
System.out.println(Arrays.toString(a));
sort(a,true);
System.out.println(Arrays.toString(a));
}
public static void sort(Comparable[] list,boolean asc) {
Comparable[] aux = new Comparable[list.length];
mergeSort(list, aux, 0, list.length-1,asc);
}
private static void mergeSort(Comparable[] list,Comparable[] aux, int start, int end,boolean asc) {
if(end <= start) {
return ;
}
int mid = (start+end)/2;
mergeSort(list,aux,start,mid,asc);
mergeSort(list,aux,mid+1,end,asc);
merge(list,aux,start,mid,end,asc);
}

private static void merge(Comparable[] list, Comparable[] aux, int start, int mid, int end, boolean asc) {
for (int i = start; i <= end; i++) {
aux[i] = list[i];
}
int i = start;
int j = mid + 1;
for (int k = start; k <= end; k++) {
if (i > mid)
list[k] = aux[j++];
else if (j > end)
list[k] = aux[i++];
else if (asc ? aux[j].compareTo(aux[i]) < 0 : aux[j]
.compareTo(aux[i]) > -1)
list[k] = aux[j++];
else
list[k] = aux[i++];
}
}

}