2）一趟二路归井排序有序子表长度为len R[0..n-1]中共分为[n/len]个有序的子表段1段2R[0..len-1]R[len..2len-1]起始i=0R[2len..3len-1]R[3len..4len-1]起始i=2lenI起始=i+2lenR[i..i+len-1]R[i+len..i+2len-1]段2的尾元素序号+21en-1<n是满的（两个段均含1en个元素）i+len-1<n-1（或者i+len<n）剩余两个有序子表否则说明仅剩余一个有序子表（第2段为空），不趟不参与归并6/41
有序子表长度为len R[0.n-1]中共分为n/len个有序的子表 段2的尾元素序号i+2len-1<n 是满的（两个段均含len个元素） i+len-1<n-1（或者i+len<n） 剩余两个有序子表 否则说明仅剩余一个有序子表（第2段为空），不趟不参与归并 R[0.len-1] R[len.2len-1] R[2len.3len-1] R[3len.4len-1] 起始i=0 起始i=2len 段1 段2 R[i.i+len-1] R[i+len.i+2len-1] 起始i=i+2len 6/41
1/一趟二路归并排序private void MergePass(int len)( int i;//归并1en长的两相邻子表for（i=0;i+2*len-1<n;i=i+2*len）Merge(i,i+len-1,i+2*len-1);if(i+len<n)//余下两个子表，后者长度小于len//归并这两个子表Merge(i,i+len-1,n-1);7/41
private void MergePass(int len) //一趟二路归并排序 { int i; for (i=0;i+2*len-1<n;i=i+2*len) //归并len长的两相邻子表 Merge(i,i+len-1,i+2*len-1); if (i+len<n) //余下两个子表,后者长度小于len Merge(i,i+len-1,n-1); //归并这两个子表 } 7/41
3）二路归井排序1/对R[0..n-11按递增进行二路归并算法public void MergeSorti()1/进行1og2n（取上界）趟归井for（intlen=1;len<n;len=2*len）MergePass(len);8/41
public void MergeSort1() //对R[0.n-1]按递增进行二路归并算法 { for (int len=1;len<n;len=2*len) //进行log2n(取上界)趟归并 MergePass(len); } 8/41
算法分析3.1二路归并排序中，长度为n的排序表需做1og,n趟，对应的归并树高度为[1og2nl，每趟归并时间为o(n)。每趟为o(n)「1og2n]趟时间复杂度的最好、最坏和平均情况都是o(nlog2n)。9/41
3. 算法分析 二路归并排序中，长度为n的排序表需做log2n趟，对应的归并树高度为 log2n，每趟归并时间为O(n)。 时间复杂度的最好、最坏和平均情况都是O(nlog2n)。 log2n趟 每趟为O(n) 9/41
归并排序过程中每次调用Merge都需要使用局部数组R1，但执行完后其空间被释放，但最后一趟排序一定是全部n个元素参与归并，所以总的辅助空间复杂度为o(n)。1822034123216156182034123261615134218206121632151216618203234151215161820343210/41
归并排序过程中每次调用Merge都需要使用局部数组R1，但执行完后其空 间被释放，但最后一趟排序一定是全部n个元素参与归并，所以总的辅助 空间复杂度为O(n)。 18 2 20 34 12 32 6 16 1 15 2 18 20 34 12 32 6 16 1 15 2 18 20 34 6 12 16 32 1 15 2 6 12 16 18 20 32 34 1 15 1 2 6 12 15 16 18 20 32 34 10/41