1. 3-way Mergesort (8 points) Consider the following variant of mergesort, where
ID: 3873513 • Letter: 1
Question
1. 3-way Mergesort (8 points) Consider the following variant of mergesort, where the fhrst call is 3wayMergesort (0,n-1,A) to sort the array AI0.n int 3wayMergesort (int i, int j, intll A)C if(j-i>-2)1 // At least 2 elements in A // Sort A[i..j] int l = (j-1)/3 ; 3wayMergesort(i,itl, A); 3wayMergesort(i+1+1,i+2*1,A); 3wayMergesort(i+2*1+1,j,A); merge(i,i+1+1,i+2*1+1); // Merges all three sub-arrays in linear time (a) Set up a runtime recurrence for 3-vay mergesort above. (b) Use the recursion tree method to find a good guess for the runtime of 3wayMergesortExplanation / Answer
Recurrence relation: T(n) = 3T(n/3) + O(n)
Runtime=O(nlogn) ,where logn has the base 3
The recurrence tree will have the height logn with base 3.
At each level O(n) work needs to be done.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.