**Problem:**

3-way-Merge Sort : Suppose that instead of dividing in half at each step of Merge Sort, you divide into thirds, sort each third, and finally combine all of them using a three-way merge subroutine. What is the overall asymptotic running time of this algorithm? (Hint: Note that the merge step can still be implemented in time.)

**Solution:**

Step 1: Write down the recurrence

Step 2: Assuming , simplify the recurrence

Let , therefore, we have

Step 3: We solve the recurrence

--

Posted By Blogger to HDGEM at 3/06/2017 09:09:00 PM