public class MergeSort {
    public static void MergeSort(int A[],int low,int high){
        if(low<high){
            int middle=(low+high)/2;
            MergeSort(A,low,middle);
            MergeSort(A,middle+1,high);
            Merge(A,low,middle,high);
        }
    }
    public static void Merge(int A[],int low,int middle,int high){
        int B[]=new int[high-low+1];
        int k=0;
        int i=low,j=middle+1;
        while(i<=middle&&j<=high)
            B[k++]=A[i]<A[j]?A[i++]:A[j++];
        while(i<=middle)
            B[k++]=A[i++];
        while(j<=high)
            B[k++]=A[j++];
        i=low;
        k=0;
        while(i<=high)
        A[i++]=B[k++];
    }
}

public class MergeSortUpgrade {
    public static void MergeSortUpgrade(int A[]){
        int s=1;
        while(s<A.length){
            MergePass(A,s);
            s+=s;
        }
    }
    public static void MergePass(int A[],int s){
        int n=A.length;
        int i;
        for( i=0;i<=n-2*s;i=i+2*s)
            Merge(A,i,i+s-1,i+2*s-1);
        if(i+s<n)Merge(A,i,i+s-1,n-1);
    }
    public static void Merge(int A[],int first,int middle,int end){
        int B[]=new int[end-first+1];
        int i=first,j=middle+1,k=0;
        while(i<=middle&&j<=end)
            B[k++]=A[i]<A[j]?A[i++]:A[j++];
        while(i<=middle)
            B[k++]=A[i++];
        while(j<=end)
            B[k++]=A[j++];
        i=first;k=0;
        while(i<=end)
            A[i++]=B[k++];
    }
}