class Mc{

    void mergeSort(int a[],int left,int right){
    if(left<right){
        int i =(left+right)/2;
        int[] b=new int[a.length];
        mergeSort(a,left,i);
        mergeSort(a,i+1,right);
        merge(a,b,left,i,right);
        copy(a,b,left,right);
    }
    }

    void merge(int c[],int d[],int l,int m,int r){
        int i=l,
            j=m+1,
            k=l;

        while((i<=m)&&(j<=r))
            if(c[i]<=c[j])
                d[k++]=c[i++];
            else d[k++]=c[j++];
        if(i>m)
            for(int q=j;q<=r;q++)
                d[k++]=c[q];
        else
            for(int q=i;q<=m;q++)
                d[k++]=c[q];

    }

    void copy(int a[],int b[],int l,int r){
        for(int i=l;i<=r;i++){
            a[i]=b[i];
        }
    }

public static void main(String[] args) {
    int [] a={6,8,3,1,8,9,3,6,1};
    Mc mc=new Mc();
    mc.mergeSort(a, 0, a.length-1);
    for(int i=0;i<a.length;i++){
        System.out.print(" "+a[i]);
    }
}
}