試題詳解

38. Professor Chen uses the following algorithm for merging k sorted lists, each having n/k elements. He takes the first list and merges it with the second list using a linear-time algorithm for merging two sorted lists, such as the merging algorithm used in merge sort. Then, he merges the resulting list of 2n/k elements with the third list, merges the list of 3n/k elements that results with the fourth list, and so forth, until she ends up with a single sorted list of all elements. What is the worst-case running time of the professor Chen's algorithm in terms of n and k.
(A)θ(log(nk))
(B)θ(nk)
(C)θ(nlogk)
(D)θ(lognlogk)
(E)θ(n)