class Sort{
public static void mergSort(Comparable a[],int left,int right){
        if(left<right){
                int i=(left+right)/2;
                mergeSort(a,left,i);
                mergeSort(a,i+1,right);
                merge(a,b,left,i,right);
                copy(a,b,left,right);
                }
        }
pulic static void mergeSort(Comparable[] a){
        Comparable[] b=new Comparable[a.lenth];
        int s=1;
        while(s<a.length){
                mergePass(a,b,s);
                s+=s;
                mergePass(b,a,s);
                s+=s;
                }
        }
public static void mergePass(Comparable[] x,Comparable[] y,int s){
        int i=0;
        while(i<=x.length-2*s){
                merge(x,y,i,i+s-1,i+2*s-1);
                i=i+2*s;       
                }
        if(i+s<x.length)
        merge(x,y,i,i+s-1,x.length-1);
        else
        for(int j=i;j<x.length;j++)
        y[j]=x[j];
        }
public static void merge(Comparable[] c,Comparable[] d,int l,int m,int r){
        int i=l;
        j=m+1;
        k=l;
        while((i<=m)&&(j<=r))
        if(c[i].compareTo(c[j])<=0)
        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];
        }
}

class Sort{
public static void mergSort(Comparable a[],int left,int right){
        if(left<right){
                int i=(left+right)/2;
                mergeSort(a,left,i);
                mergeSort(a,i+1,right);
                merge(a,b,left,i,right);
                copy(a,b,left,right);
                }
        }
pulic static void mergeSort(Comparable[] a){
        Comparable[] b=new Comparable[a.lenth];
        int s=1;
        while(s<a.length){
                mergePass(a,b,s);
                s+=s;
                mergePass(b,a,s);
                s+=s;
                }
        }
public static void mergePass(Comparable[] x,Comparable[] y,int s){
        int i=0;
        while(i<=x.length-2*s){
                merge(x,y,i,i+s-1,i+2*s-1);
                i=i+2*s;       
                }
        if(i+s<x.length)
        merge(x,y,i,i+s-1,x.length-1);
        else
        for(int j=i;j<x.length;j++)
        y[j]=x[j];
        }
public static void merge(Comparable[] c,Comparable[] d,int l,int m,int r){
        int i=l;
        j=m+1;
        k=l;
        while((i<=m)&&(j<=r))
        if(c[i].compareTo(c[j])<=0)
        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];
        }
}