Java中常用的6种排序算法详细分解(5)

/** 
* Merge sorting 
*/
MERGE(new Sortable() { 
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { 
        this.sort(array, 0, array.length – 1, ascend); 
    } 
 
    private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) { 
        // OPTIMIZE ONE 
        // if the substring's length is less than 20, 
        // use insertion sort to reduce recursive invocation 
        if (hi – lo < 20) { 
            for (int i = lo + 1; i <= hi; i++) { 
                T toInsert = array[i]; 
                int j = i; 
                for (; j > lo; j–) { 
                    int compare = array[j - 1].compareTo(toInsert); 
                    if (compare == 0 || compare < 0 == ascend) { 
                        break; 
                    } 
                    array[j] = array[j - 1]; 
                } 
 
                array[j] = toInsert; 
            } 
 
            return; 
        } 
 
        int mid = lo + (hi – lo) / 2; 
        sort(array, lo, mid, ascend); 
        sort(array, mid + 1, hi, ascend); 
        merge(array, lo, mid, hi, ascend); 
    } 
 
    private <T extends Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) { 
        // OPTIMIZE TWO 
        // if it is already in right order, skip this merge 
        // since there's no need to do so 
        int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]); 
        if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) { 
            return; 
        } 
 
        @SuppressWarnings("unchecked") 
        T[] arrayCopy = (T[]) new Comparable[hi - lo + 1]; 
        System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length); 
 
        int lowIdx = 0; 
        int highIdx = mid – lo + 1; 
 
        for (int i = lo; i <= hi; i++) { 
            if (lowIdx > mid – lo) { 
                // left sub array exhausted 
                array[i] = arrayCopy[highIdx++]; 
            } else if (highIdx > hi – lo) { 
                // right sub array exhausted 
                array[i] = arrayCopy[lowIdx++]; 
            } else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) { 
                array[i] = arrayCopy[lowIdx++]; 
            } else { 
                array[i] = arrayCopy[highIdx++]; 
            } 
        } 
    } 
})