public class MergeComparable{

    public static void sort(int[] a){
        
        if (a.length <= 1) 
            return;

        int mid=a.length/2;

        int[] left=new int[mid];
        int[] right=new int[a.length-mid];

        for (int i=0; i<mid; i++)
            left[i]=a[i];

        for (int i=0; i<right.length; i++)
            right[i]=a[mid+i];

        sort(left);
        sort(right);
        merge(left,right,a);
        
    }

    public static void merge(int []a, int[] b, int[] dest){
        
        int aIndex=0;
        int bIndex=0;

        while(aIndex+bIndex < dest.length){
            boolean chooseA=true;
            
            if(aIndex >= a.length){
                chooseA = false;
            } else if (bIndex >= b.length){
                chooseA = true;
            } else { 
                chooseA = (a[aIndex] <= b[bIndex]);
            }
            
            if (chooseA){
                dest[aIndex+bIndex]=a[aIndex];
                aIndex++;
            } else {
                dest[aIndex+bIndex]=b[bIndex];
                bIndex++;
            }

        }
                
        
    }

        
}