归并排序

Divide array into two halves.
Recursively sort each other.
Merge two halves.

原地归并

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

    for(int k=lo;k<=hi;k++){
        aux[k] = a[k];   //copy
    }

    //merge back to a[]
    int i = lo; j = mid + 1;
    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(a[j],a[i]))  a[k] = aux[j++];
        else                      a[k] = aux[i++];
    }

    assert isSort(a,lo,hi);
}

归并时的四个判断：

左半边用尽(取右半边元素)
右半边用尽(取左半边元素)
右半边的当前元素小于左半边的当前元素(取右半边的元素)
右半边的当前元素大于/等于左半边的当前元素(取左半边的元素)

Assertion

can enable or disable at runtime
- java -ea MyProgram // enable assertions
- java -da MyPaogram // disable assertions(default)

public class Merge{
    private static void merge(...){
        /* as before */
    }

    private static void sort(Comparable[] a,Comparable[] aux,int lo,int hi){
        if(hi <= lo)  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(Comparablep[] a){
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0,a.length - 1);
    }
}

notes

一些改进：

对小规模子数组使用插入排序,cutoff to insertion sort for = 10 items.

private static void sort(Comparable[] a,Comparable[] aux,int lo,int hi){
        if(hi <= lo + CUTOFF - 1){
            Insertion.sort(a,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);
    }

测试数组是否已经有序（左边最大<右边最小时，直接返回）

private static void sort(Comparable[] a,Comparable[] aux,int lo,int hi){
        if(hi <= lo)  return;
        int mid = lo + (hi - lo) / 2;
        sort(a,aux,lo,mid);
        sort(a,aux,mid+1,hi);
        if(!less(a[mid+1],a[mid]))  return;
        merge(a,aux,lo,mid,hi);
    }

不将元素复制到辅助数组(节省时间而非空间)

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

    int i = lo; j = mid + 1;
    for(int k=lo;k<=hi;k++){
        //merge from a[] to aux[]
        if(i > mid)               aux[k] = a[j++];
        else if(j > hi)           aux[k] = a[i++];
        else if(less(a[j],a[i]))  aux[k] = a[j++];
        else                      aux[k] = a[i++];
    }

}

private static void sort(Comparable[] a,Comparable[] aux,int lo,int hi){
    //assumes aux[] is initialize to a[] once,before recursive calls.
    if(hi <= lo)  return;
    int mid = lo + (hi - lo) / 2;
    // switch roles of aux[] and a[]
    sort(aux,a,lo,mid);
    sort(aux,a,mid+1,hi);
    merge(a,aux,lo,mid,hi);
    }

bottom-up mergesort

notes

public class MergeBU{
    private static void merge(...){
        /* as before */
    }

    public static void sort(Comparable[] a){
        int N = a.length;
        Comparable[] aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz+sz)
            for (int lo = 0; lo < N-sz; lo += sz+sz)
                merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));

    }
}