兩路歸并的遞歸算法：

　　【算法10.13】

　　void MSort(ElemType *p，ElemType *p1，int s，int t)

　　{ /*將p[s…t]歸并排序為p1[s…t]*/

　　if(s==t) p1[s]=p[s]

　　else

　　{ m=(s+t)/2; /*平分*p表*/

　　MSort(p，p2，s，m); /*遞歸地將p[s…m]歸并為有序的p2[s…m]*/

　　MSort(p，p2，m+1，t); /*遞歸地將p[m+1…t]歸并為有序的p2[m+1…t]*/

　　Merge(p2，p1，s，m+1，t); /*將p2[s…m]和p2[m+1…t]歸并到p1[s…t]*/

　　}

　　}

　　void MergeSort(S_TBL *p)

　　{ /*對順序表*p作歸并排序*/

　　MSort(p->elem，p->elem，1，p->length);

　　}

　　【效率分析】

　　需要一個與表等長的輔助元素數組空間，所以空間復雜度為O(n)。

　　對n個元素的表，將這n個元素看作葉結點，若將兩兩歸并生成的子表看作它們的父結點，則歸并過程對應由葉向根生成一棵二叉樹的過程。所以歸并趟數約等于二叉樹的高度-1，即log2n，每趟歸并需移動記錄n次，故時間復雜度為O(nlog2n)。

　　基數排序：

　　基數排序是一種借助于多關鍵碼排序的思想，是將單關鍵碼按基數分成“多關鍵碼”進行排序的方法。

　　多關鍵碼排序：

　　設n個元素的待排序列包含d個關鍵碼{k1，k2，…，kd}，則稱序列對關鍵碼{k1，k2，…，kd}有序是指：對于序列中任兩個記錄r[i]和r[j](1≤i≤j≤n)都滿足下列有序關系：

　　其中k1稱為最主位關鍵碼，kd稱為最次位關鍵碼。

　　多關鍵碼排序按照從最主位關鍵碼到最次位關鍵碼或從最次位到最主位關鍵碼的順序逐次排序，分兩種方法：

　　最高位優先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關鍵碼k1相等，再對各組按k2排序分成子組，之后，對后面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd對各子組排序后。再將各組連接起來，便得到一個有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD法。

　　最低位優先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序后便得到一個有序序列。撲克牌按花色、面值排序中介紹的方法二即是LSD法。

　　　　　　　計算機軟考軟件設計師練習試題及答案解析匯總