扩展二路归并I推广多路归并三路归并的归并树的高度为[1og3nl，同样一次三路归并的时间为o(n),所以三路归并排序的时间复杂度为o(nlog3n)。而nlogn=nlog2n/log23，即o(nlog3n)=o(nlog2n)，也就是说，三路归并排序与二路归并排序的时间复杂度相同。11/41
三路归并的归并树的高度为log3n，同样一次三路归并的时间为O(n)， 所以三路归并排序的时间复杂度为O(nlog3n)。 而nlog3n=nlog2n/log23，即O(nlog3n)=O(nlog2n)，也就是说，三路 归并排序与二路归并排序的时间复杂度相同。 二路归并 多路归并 推广 11/41
1563728412/41
12/41
自顶向下的二路归并排序10.5.2排序区间是R[s..t]（为大问题），当其长度为0或者1时，本身就是有序的，不做任何处理。否则，其中间位置m，采用相同方法对R[s..m]和R[m+1..t]排好序（分解为两个小问题），再调用前面的二路归并算法Merge(s，m，t)得到整个有序表（合并）。f(R，S，t）=不做任何事情当R[s..t1为空或者仅有一个元素时其他情况f(R, S, t) = m=(s+t)/2;f(R, S, m); f(R, m+1, t);Merge(s, m, t);13/41
排序区间是R[s.t]（为大问题），当其长度为0或者1时，本身就是有 序的，不做任何处理。 否则，其中间位置m，采用相同方法对R[s.m]和R[m+1.t]排好序（分 解为两个小问题），再调用前面的二路归并算法Merge(s，m，t)得到整 个有序表（合并）。 f(R，s，t) ≡ 不做任何事情 当R[s.t]为空或者仅有一个元素时 f(R，s，t) ≡ m=(s+t)/2; 其他情况 f(R，s，m); f(R，m+1，t); Merge(s，m，t); 13/41
1/对R[0..n-1]按递增进行二路归并算法public void MergeSort2()+MergeSort21(0,n-1);71/被MergeSort2调用private void MergeSort2(int s,int t)//R[s..t]的长度为0或者1时返回if(s>=t)return;玩int m=(s+t)/2;1/取中间位置m1/对前子表排序MergeSort21(s,m);//对后子表排序MergeSort21(m+1,t);Merge(s,m,t);//将两个有序子表合并成一个有序表递归二路归并排序方法14/41
public void MergeSort2() //对R[0.n-1]按递增进行二路归并算法 { MergeSort21(0,n-1); } private void MergeSort21(int s,int t) //被MergeSort2调用 { if(s>=t) return; //R[s.t]的长度为0或者1时返回 int m=(s+t)/2; //取中间位置m MergeSort21(s,m); //对前子表排序 MergeSort21(m+1,t); //对后子表排序 Merge(s,m,t); //将两个有序子表合并成一个有序表 } 递归二路归并排序方法 14/41