- 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));
}
}
}
