3. Consider the following sort algorithm for large arrays: HybridSort. Hy- bridS

Question

3. Consider the following sort algorithm for large arrays: HybridSort. Hy- bridSort is a combination of MergeSort and Insertion Sort. The original MergeSort algorithm recurses until the size of each subarray is only 1. Hy- bridSort is the same as MergeSort, except that it only recurses to a depth of at most r, where r is some fixed constant i.e., the depth of the recursion tree is at most r). At that point, Insertion Sort is used for the resulting subproblems. For example, if after performing recursions to a depth of r, the resulting subarrays have size 5, InsertionSort is used on each of those size-5 subarrays. The sorted results are then returned to the MergeSort recursion tree and merged as in the original MergeSort What is the running time of this algorithm as a function of n

Explanation / Answer

Solution:

Since the merge sort is being performed until the depth of r, then the complexity till here will be

O(n log r)

and then insertion sort is applied for sorting subarrays for the rest of the recursive tree.

which will consume O(n-r)^2 of time.

So final time complexity will be

T(n) = O(n log r) + (n-r)^2

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.