Mergesort has the following recurrence equation in the worst case: W(n) = 2W(n/2
ID: 1944262 • Letter: M
Question
Mergesort has the following recurrence equation in the worst case:W(n) = 2W(n/2) + n - 1
W(1) = 0
We saw that this has the solution W(n) = n lg n - n + 1, so W(n) ?T(n log n).
Consider Ternary Mergesort, where an array of n numbers is divided approximately in
thirds, each third is divided into subarrays one-third the size, etc. until single items are
reached. Then the merge operation proceeds upward merging 3 smaller arrays into a
single larger array until, at the top, the entire array is sorted.
A worst case instance in the merge process might appear as follows:
1 4 7 10 2 5 8 11 3 6 9 12
First 1 is compared to 2, and then the smaller (1) is compared to 3. The smallest (1) is
placed in the larger array. Then 4 is compared to 2, and 2 is compared with 3, so 2
becomes the next item after 1 in the larger array, and so on.
In general, for n items in three arrays each of size n/3, how many total comparisons will
there be in the worst case (as a function of n)?
Using this value and taking a comparison as the basic operation, write a recurrence
equation for the worst case of Ternary Mergesort and solve it by the substitution method.
You may assume for simplicity that n is a power of 3.
Check the correctness of your result by mathematical induction. Find its T-category and
check your answer using the Master Theorem.
Would Ternary Mergesort have any advantages over standard Binary Mergesort?
It may be helpful to know that log10 2 is approximately 0.3010 and log10 3 is
approximately 0.4771.
Explanation / Answer
no its doesnt when ternary W(n) = 3W(n/3) + n - 1 ==> W(n) = T(n log n) even if W(n) = 99W(n/99) + n - 1 then also same answer