申論題

3. (3 points) We now use the merge algorithm in the previous question to sort a set of keys. We irst make each key a list of a single node. Then we merge the first and the second lists into a sorted list of length two, the third and the fourth lists into a sorted list of length two, and so on. If we start with n keys now we have roughly n/2 sorted list of length two now. We then merge these lists of length two into roughly n/4 sorted list of length four, and so on. Finally we will have a sorted list of length n. Let f(n) denote the mazimum possible total number of comparisons of this algorithm, then f(n) is? Note that all the answers are in little-o notation. 1.o(n)
2.
 3.o(nlogn)
 4.o(n(logr)²) 5.o(n²)