归并排序及其可视化

$$以下实现的归并排序的空间复杂度O(n)\&＃xff0c;需要O(n)的辅助空间$$

• 同一颜色表示排好序的一个块
  

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


自底向上的归并排序&＃xff1a;
void MerGesort(T a[],int n)
{int t&＃61;1;while(t<n){s&＃61;t;t&＃61;s*2;for(i&＃61;0;i&＃43;t<n;i&＃43;&＃61;t)Merge(a,i,i&＃43;s-1,i&＃43;t-1);if(i&＃43;s<n)Merge(a,i,i&＃43;s-1,i&＃43;t-1);}
}


归并排序&＃xff1a;
void MerGesort(T a[],int low,int high)
{if(low>&＃61;high) return;else{mid&＃61;(low&＃43;high)/2;MergeSort(a,low,mid);MergeSort(a,mid&＃43;1,high);Merge(a,low,mid,high);}
}


递归的过程

void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){int i &＃61; startIndex, j&＃61;midIndex&＃43;1, k &＃61; startIndex;while(i!&＃61;midIndex&＃43;1 && j!&＃61;endIndex&＃43;1) {if(sourceArr[i] > sourceArr[j])tempArr[k&＃43;&＃43;] &＃61; sourceArr[j&＃43;&＃43;];elsetempArr[k&＃43;&＃43;] &＃61; sourceArr[i&＃43;&＃43;];}while(i !&＃61; midIndex&＃43;1)tempArr[k&＃43;&＃43;] &＃61; sourceArr[i&＃43;&＃43;];while(j !&＃61; endIndex&＃43;1)tempArr[k&＃43;&＃43;] &＃61; sourceArr[j&＃43;&＃43;];for(i&＃61;startIndex; i<&＃61;endIndex; i&＃43;&＃43;)sourceArr[i] &＃61; tempArr[i];
}

T(n)&＃61;aT(nb)&＃43;f(n)T(n)&＃61;aT(\frac{n}{b})&＃43;f(n) T(n)&＃61;aT(bn​)&＃43;f(n)
$$则有\&＃xff1a;⎩$$

⎨

⎧​O(nlogb​a)O(f(n)logn)O(f(n))​O(nlogb​a)>O(f(n))O(nlogb​a)&＃61;O(f(n))O(nlogb​a)<O(f(n))​