Please show your detailed work I will rate correct answers T

Please show your detailed work! I will rate correct answers! Thank you.

Let X_1, X_2, ...X_t be sorted files with sigma^t _i=1 |X_i |=n. (So the total number of objects in all files is n.) Describe an O(n log t) time algorithm divide and conquer algorithm for merging all these files into one file. (Assume that you have a standard merge algorithm for merging 2 sorted files.)

Solution

Adding elements to a priority queue can be done in logarithmic time, item 2 is O(t × log t). Since (almost all) iterations of the while loop adds an element, the whole while-loop is O(n × log t)where n is the total number of numbers to sort.

Assuming all files have a non-empty sequence of numbers, we have n> t and thus the whole algorithm should be O(n × log t).