① 简述二路归并排序，并分析其算法复杂性。
二路归并，就是将两个有序序列，合并为一个有序的序列
而排序最初是一个无序序列，此时就要将其分解为两个有序序列
这里就用到一个递归的思想
即：将该算法截为两段，对前后两段应用该算法均可得到一个有序序列，这是就有了两个有序序列，再使用该算法就最终得到一个有序序列
而递归终点是当分段内只有一个元素时，显然就是有序序列了，就可以返回
具体的代码为：
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我