1
$\begingroup$

enter image description here

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)

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.