一组经过第一趟 2-路归并排序后的记录的关键字为 (25,50,15,35,80,85,20,40,36,70)，其中包含 5 个长度为 2 的有序序，用 2-路归并排序方法对该序列进行第二趟归并后的结果为（ ）。

A. 15,25,35,50,80,20,85,40,70,36

B. 15,25,35,50,20,40,80,85,36,70

C. 15,25,50,35,80,85,20,36,40,70

D. 15,25,35,50,80,20,36,40,70,85

归并排序

[tag_link]

正确答案：B

首先，第一趟归并后得到序列 ( 25 , 50 , 15 , 35 , 80 , 85 , 20 , 40 , 36 , 70 ) 其中包含 5 个长度为 2 的有序子序列，分别为： ( 25 , 50 ) , ( 15 , 35 ) , ( 80 , 85 ) , ( 20 , 40 ) , ( 36 , 70 ) 在第二趟 2-路归并中，需要将相邻的有序子序列两两合并。 具体来说： 合并第一个和第二个子序列：将 ( 25 , 50 ) 和 ( 15 , 35 ) 合并，得到有序序列 ( 15 , 25 , 35 , 50 ) 合并第三个和第四个子序列：将 ( 80 , 85 ) 和 ( 20 , 40 ) 合并，得到有序序列 ( 20 , 40 , 80 , 85 ) 第五个子序列 ( 36 , 70 ) 没有相邻配对，保持原样。 因此，第二趟归并后的序列由三个有序子序列依次组成： ( 15 , 25 , 35 , 50 ) , ( 20 , 40 , 80 , 85 ) , ( 36 , 70 ) , 整体为 15 , 25 , 35 , 50 , 20 , 40 , 80 , 85 , 36 , 70 对比选项，B 与此一致。