Constructing a Divide and Conquer Algorithm

Question

I'm thinking of using something similar to the Merge Sort algorithm. So the recurrence running time of Merge Sort is T(n) = 2T(n/2) + n. What should I do about if n/2 is less than or equal to m, OR if n/2 is greater than or equal to m?

I believe the given function should be location inside the "Merge" function of the Merge Sort.(Since we're merging a sorted array) Thank you for your time.

Edited: I'm thinking if n/2 is less than or equal to m, use the "Given" function . Otherwise use the original "Merge" function (The usual Merge for Merge Sort)

Answer 1

I believe you have misunderstood the question. The magical merge algorithm merges two lists of size $m$ in time $m^{1-\epsilon}$ for every possible $m$ (of course, such an algorithm is impossible). Since merging usually takes linear time $O(m)$, it is always better to replace it with the magical merge algorithm. You then get a different recurrence for your magical merge sort, and the running time should come out linear rather than $O(n\log n)$.