p175算法2.2.3自底向上归并排序

public class MergeBU {
    public static void sort(Comparable[] a){
        int N = a.length;
        for(int sz = 1;sz<N;sz = sz+sz){ //sz子数组大小
            for(int lo = 0;lo<N-sz;lo+=sz+sz){//lo子数组索引
                merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1, N-1));
            }
        }
    }
    private static void merge(Comparable[] a, int lo,int mid, int hi) {
        Comparable[] aux = new Comparable[a.length];
        int i = lo,j=mid+1;
        for(int k = lo;k<=hi;k++){
            aux[k] = a[k];
        }
        for(int k = lo; k<=hi;k++){
            if(i > mid)
                a[k] = aux[j++];
            else if(j > hi)
                a[k] = aux[i++];
            else if(less(aux[i],aux[j]))
                a[k] = aux[i++];
            else
                a[k] = aux[j++];
        }
        
    }
    private static boolean less(Comparable v, Comparable w) {
        // TODO Auto-generated method stub
        return v.compareTo(w) < 0;
    }
    public static void main(String[] args) {
        Integer[] a = new Integer[]{888,494,110,12,154,123,456,356,486,576,16,654,23,451,};
        sort(a);
        for(int num : a){
            System.out.print(" "+num);
        }
    }

}