merge sort 归并排序

• basic merg sort
  给两个排好序的序列，将它们混合排序好 NlogN

public void mergeSort(int a[],int[] aux,int io,int mid,int hi){
    //precondition:a[lo……mid]，a[mid+1……hi] is sorted
    for(int i=lo;i<=hi;i++){
        aux[i] = a[i]
    }
    int p = lo,q = mid+1;
    for(int i=lo;i<=hi;i++){
        if(i>mid) a[i] = aux[q++];
        else if(q>hi) a[i] = aux[p++];
        else if(aux[p]<=aux[q]) a[i] = aux[p++];
        else a[i] = aux[q++];
    }
    
}

利用递归实现merge sort：

public void sort(int[] a,int[] 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 void sort(int[] a){
    int aux = new int[a.length];
    sort(a,aux,0,a.length-1);
}

• bottom up merge sort
  不用递归，从1开始merge，然后是2，会得到一堆长度为2并且排好序的subarrays，然后是4，得到一堆长度为4的排好序的subarrays……
  merge的代码和上面相同，不同的是sort的代码：

public void sort(int[] a){
    int N = a.length;
    for(int size = 1;size<N;size = size+size){
        for(int lo = 0;lo<N-size;lo=lo+size+size){
            merge(a,lo,lo+size-1;Math.min(lo+size+size-1,N-1));
        }
    }
}