① 簡述二路歸並排序，並分析其演算法復雜性。
二路歸並，就是將兩個有序序列，合並為一個有序的序列
而排序最初是一個無序序列，此時就要將其分解為兩個有序序列
這里就用到一個遞歸的思想
即：將該演算法截為兩段，對前後兩段應用該演算法均可得到一個有序序列，這是就有了兩個有序序列，再使用該演算法就最終得到一個有序序列
而遞歸終點是當分段內只有一個元素時，顯然就是有序序列了，就可以返回
具體的代碼為：
void Merge(int r[],int r1[],int s,int m,int t)//二路歸並
{
int i=s,j=m+1,k = s;
while(i<=m && j<=t)
{
if (r[i] <= r[j]) r1[k++] = r[i++];
else r1[k++] = r[j++];
}
if(i <= m)
{
while(i <= m)
r1[k++] = r[i++];
}
else
{
while (j <= t)
r1[k++] = r[j++];
}
}
void MergeSort(int r[],int r1[],int s,int t)//遞歸調用
{
if(s == t) r1[s] = r[s];
else{
m = (s + t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);
Merge(r1,r,s,m,t);
}
}
至於它的時間復雜度，從嚴格分析上說是O（nlog2n）,我做過測試，它在較大數據排序時，性能不亞於快排，堆排，並且和初始數據順序性無關，是一種穩定的排序演算法
至於缺點就是它的空間復雜度，達到O（n）
此外，它還有非遞歸演算法，思想都是一樣的，我就不多說了，如果你需要，可以Hi我