归并排序

public class MergeSort{
    public static void sort(int[] arr,int[] aux,int lo,int hi){
        if(lo>=hi){
            return;
        }
        int mid=lo+(hi-lo)/2;
        sort(arr,aux,lo,mid);
        sort(arr,aux,mid+1,hi);
        merge(arr,aux,lo,mid,hi);
    }    

    public static void sort(int[] a){
        int[] aux=new int[a.length];
        sort(a,aux,0,a.length-1);
    }
    public static void merge(int[] arr,int[] aux,int lo,int mid,int hi){
        int i=lo,j=mid+1;
        for(int k=lo;k<=hi;k++)
        {
            aux[k]=arr[k];
        }

        for(int k=lo;k<=hi;k++){
            if(i>mid){arr[k]=aux[j++];}
            else if(j>hi){arr[k]=aux[i++];}
            else if(aux[j]<aux[i]){arr[k]=aux[j++];}
            else{arr[k]=aux[i++];}
        }
    }
}