归并排序

package merge.sort;

public class Merge {

    private Merge() { }
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid + 1, hi);

        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        int i = lo, j = mid + 1;
        int k = lo;
        // the same as the for loop in note.sort.Merge's merge
        while (i <= mid && j <= hi){
            if (less(aux[i],aux[j])) a[k++] = aux[i++];
            else a[k++] = a[j++];
        }
        while (i <= mid) a[k++] = aux[i++];
        while(j <= hi ) a[k++] = aux[j++];
    }

    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {

        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        return isSorted(a);
    }

    private static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1]))
                return false;
        }
        return true;
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 1;
    }
    
    

    public static void main(String[] args) {
        Comparable[] A = {1,3,2,4};
        sort(A);
        for(int i = 0; i < A.length; i++)
            System.out.println(A[i]);
    }
}