Mergesort示例

/*来自 N o w  J a v a  . c o m*/

import static java.lang.System.out;


class MergeImprove {


    private static final int CUTOFF = 7;

    

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

        for (int i = lo; i <= hi; i++)

            for (int j = i; j > lo && less(a[j], a[j-1]); j--)

                exch(a, j, j-1);

    }

    

    private static void exch(Comparable[] a, int i, int j) {

        Comparable swap = a[i];

        a[i] = a[j];

        a[j] = swap;

    }

    //n o w j a   v  a . c o m - 时  代  Java 提 供

    private static boolean less(Comparable v, Comparable w) {

        return v.compareTo(w) < 0;

    }

    

    public 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 void merge(Comparable[] a, Comparable[] another, int lo, int mid, int hi) {

        int i = lo, j = mid + 1;

        

        for (int k = lo; k <= hi; k++) {

            if (i > mid)

                a[k] = another[j++];

            else if (j > hi)

                a[k] = another[i++];

            else if (less(another[j], another[i]))

                a[k] = another[j++];

            else

                a[k] = another[i++];

        }

    }

    

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

        //improvement: use insertionSort for small subarray

      if (hi <= lo + CUTOFF) { 

            insertionSort(another, lo, hi);

            return;

        }

        

        int mid = lo + (hi - lo) / 2; //split the array in 2 parts

        

        sort(a, another, lo, mid); //left

        sort(a, another, mid+1, hi); //right

        

        //improvement: array already order

        if (!less(a[mid+1], a[mid])) {

            System.arraycopy(a, lo, another, lo, hi - lo + 1);

            return;

        }

        

        merge(a, another, lo, mid, hi);

    }

    

    public static void sort(Comparable[] a) {