public class MergeSortAlgo {
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(int[] arr, int low, int mid, int high) {
int size = arr.length;
int[] temp = new int[size];
for(int i = low; i <= high; ++i) {
temp[i] = arr[i];
}
// copy to aux[]
for (int k = low; k <= high; k++) {
temp[k] = arr[k];
}
// merge back to a[]
int i = low, j = mid+1;
for (int k = low; k <= high; k++) {
if (i > mid) arr[k] = temp[j++]; // this copying is unnecessary
else if (j > high) arr[k] = temp[i++];
else if (temp[j]<temp[i])
arr[k] = temp[j++];
else arr[k] = temp[i++];
}
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(int[] a, int lo, int hi) {
if (lo<hi){
int mid = (lo+hi) / 2;
// System.out.println("Low :"+lo+" Mid: "+mid +" High :"+hi);
sort(a, lo, mid);
// System.out.println("Mid Sort ===");
sort(a, mid + 1, hi);
System.out.println("Merge ==="+lo + mid+ hi);
merge(a, lo, mid, hi);
}
}
public static void main(String args[]){
int[] arr={84,27,49,91,32,53,63,17};
//int[] arr={5,10,1,6,2,9,3,8,7,4};
// int[] arr={6,7,8,9,1,2,3,4,5};
int size=arr.length;
sort(arr, 0, arr.length-1);
//System.out.println(counter);
System.out.println("After sorting: ");
for(int i = 0; i < size; ++i) {
System.out.println(arr[i]);
}
}
}