归并排序

$$以下实现的归并排序的空间复杂度O(n)，需要O(n)的辅助空间$$

void Merge(T a[],int low,int mid,int high) //将有序序列a[low-mid],a[mid+1,high]归并到a[low,high]

自底向上的归并排序： void MerGesort(T a[],int n) { int t=1; while(t<n) { s=t;t=s*2; for(i=0;i+t<n;i+=t) Merge(a,i,i+s-1,i+t-1); if(i+s<n) Merge(a,i,i+s-1,i+t-1); } } 归并排序： void MerGesort(T a[],int low,int high) { if(low>=high) return; else { mid=(low+high)/2; MergeSort(a,low,mid); MergeSort(a,mid+1,high); Merge(a,low,mid,high); } }

递归的过程

void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){ int i = startIndex, j=midIndex+1, k = startIndex; while(i!=midIndex+1 && j!=endIndex+1) { if(sourceArr[i] > sourceArr[j]) tempArr[k++] = sourceArr[j++]; else tempArr[k++] = sourceArr[i++]; } while(i != midIndex+1) tempArr[k++] = sourceArr[i++]; while(j != endIndex+1) tempArr[k++] = sourceArr[j++]; for(i=startIndex; i<=endIndex; i++) sourceArr[i] = tempArr[i]; }

$$T(n)=aT(\frac{n}{b})+f(n)$$ $$则有：\{\begin{array}{ll}O(n^{lo{g}_{b}a})& O(n^{lo{g}_{b}a})>O(f(n))\\ O(f(n)logn)& O(n^{lo{g}_{b}a})=O(f(n))\\ O(f(n))& O(n^{lo{g}_{b}a})<O(f(n))\end{array}$$