import java.util.*;

public class MergeOrder{

public void process2(int[] arr){

int size = 1;

int length = arr.length;

while(size < length){

int left = 0;

while(left < length){

int mid = left + size -1;

if(mid > length) break;

int right = Math.min(mid+size,length-1);

merge(arr,left,mid,right);

left = right+1;

}

size=size<<1;

}

}

public void process(int[] arr,int left, int right){

if(left == right) return;

int mid = left +((right - left) >> 1);

process(arr,left,mid);

process(arr,mid+1,right);

merge(arr,left,mid,right);

}

public void merge(int[] arr, int left,int mid,int right){

int[] help = new int[right - left +1 ];

int helpi = 0;

int p1 = left;

int p2 = mid+1;

while(p1<= mid && p2<= right){

help[helpi++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];

}

while(p1<=mid){

help[helpi++] = arr[p1++];

}

while(p2<=right){

help[helpi++] = arr[p2++];

}

for (int i=0; i<help.length;i++ ) {

arr[left+i] = help[i];

}

}

public static void main(String[] args){

int[] arr={20000,3,2,5,4,8,99,600,1,99,188,230,9100,10000,9999};

MergeOrder merge = new MergeOrder();

//merge.process(arr,0,arr.length - 1);

merge.process2(arr);

for (int i=0; i<arr.length;i++ ) {

System.out.print(arr[i]+",");

}

}

}