class Main {
public static void main(String[] args) {
int[] arr=new int[]{4,7,3,8,1,0,12,45,66};
gbSort(arr,0,arr.length-1);
for(int tmp:arr){
System.out.print(tmp+",");
}
}
public static void gbSort(int[] arr,int L,int R){
if(L>=R){
return;
}
int mid=L+(R-L)/2;
gbSort(arr,L,mid);
gbSort(arr,mid+1,R);
marge(arr,L,R,mid);
}
public static void marge(int[] arr,int L,int R,int mid){
int[] tmp=new int[R-L+1];
int i=L,j=mid+1,index=0;
while(i<=mid&&j<=R){
if(arr[i]<arr[j]){
tmp[index++]=arr[i++];
}else{
tmp[index++]=arr[j++];
}
}
while(i<=mid){
tmp[index++]=arr[i++];
}
while(j<=R){
tmp[index++]=arr[j++];
}
for(int x=0;x<tmp.length;x++){
arr[L+x]=tmp[x];
}
}
}