import java.util.Arrays;
public class MergeSort {
public static int[] arr = {3, 2, 4, 1, 6, 8, 0};
public static int[] aux = new int[arr.length];
/*
* aux[7]
* 1,2,3,4, 0,6,8
* mid = lo + (hi - lo)/2
* 3, 2, 4, 1, 6, 8, 0
* 3, 2, 4, 1
* 3, 2
* 3
* 2
* 2,3
* 4
* 1
* 1,4
* 1,2,3,4
* 6, 8
* 6
* 8
* 6,8
* 0
* 0,6,8
* 0,1,2,3,4,6,8
*
* compare: (NlogN)/2, NlogN
* array access: (2N + 2N + 2N)logN = 6NlogN
*/
private static void merge(int[] a, int lo, int mid, int hi){
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
int i = lo;
int j = mid + 1;
for (int k = lo; k <= hi; k++) {
if(i > mid) a[k] = aux[j++];
else if(j > hi) a[k] = aux[i++];
else if(aux[j] <= aux[i]) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
private static void sort(int[] a, int lo, int hi){
int mid = lo + (hi - lo)/2;
if(lo >= hi) return;
sort(a, lo, mid);
sort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
public static int[] sort(int[] a) {
sort(a, 0, a.length -1);
return a;
}
public static void main(String[] args) {
Arrays.stream(sort(arr)).forEach(System.out::println);
}
}
