import java.util.*;
public class Main {
public static void main(String args[]) {
// Your Code Here
int[] A = {3, 6, 4, 1, 2};
int[] ans = MergeSort(A , 0, A.length-1);
for(int s : ans){
System.out.print(s + " ");
}
}
public static int[] MergeSort(int[] array, int lo, int hi){
if(lo==hi){
int[] br = new int[1];
br[0] = array[lo];
return br;
}
int mid = (lo+hi)/2;
int[] fh = MergeSort(array, lo, mid);
int[] sh = MergeSort(array, mid+1, hi);
int[] merge = MergeTwoSortedArray(fh, sh);
return merge;
}
public static int[] MergeTwoSortedArray(int[] arr1, int[] arr2){
int i=0, j=0, k=0;
int[] merged = new int[arr1.length + arr2.length];
while(i<arr1.length && j<arr2.length){
if(arr1[i] < arr2[j]){
merged[k] = arr1[i];
i++;
k++;
}else{
merged[k] = arr2[j];
j++;
k++;
}
}
if(i==arr1.length){
while(j<arr2.length){
merged[k] = arr2[j];
j++;
k++;
}
}else{
while(i<arr1.length){
merged[k]=arr1[i];
i++;
k++;
}
}
return merged;
}
}