- basic merg sort
給兩個(gè)排好序的序列而柑，將它們混合排序好 NlogN
public void mergeSort(int a[],int[] aux,int io,int mid,int hi){
//precondition:a[lo……mid]曼氛，a[mid+1……h(huán)i] 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++];
}
}
利用遞歸實(shí)現(xiàn)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奢讨，會(huì)得到一堆長(zhǎng)度為2并且排好序的subarrays蔚鸥，然后是4庞瘸，得到一堆長(zhǎng)度為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));
}
}
}
