单选题 对由n个元素所组成的序列按排序码排序时，二路归并排序算法的排序码平均比较次数为______，所需要的辅助存储是O(n)。
  • A.O(1)
  • B.O(nlog2n)
  • C.O(n)
  • D.O(n2)
【正确答案】 B
【答案解析】[解析] 二路归并排序是将初始序列看成n个有序的子序列，每个子序列的长度为1，然后两两合并，得到[n/2]个长度为2的有序子序列，最后一个长度为0或1；再两两合并，如此重复，直至得到一个长度为n的有序序列为止。其时间复杂度为O(nlog2n)。二路归并排序需要有和待排序记录等数量的存储空间，因而为O(n)。