The Algorithm Design Manual (3rd) Exercise Solution 'E4-28'

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-28

Question

Consider the following modification to merge sort: divide the input array into thirds (rather than halves), recursively sort each third, and finally combine the results using a three-way merge subroutine. What is the worst-case running time of this modified merge sort?

Solution

The height of its recursion tree becomes $\lceil\log_3{n}\rceil$.
Merge algorithm for three way merging is similar to that of two way merging, but requires double amount of comparisons. Here we roughly estimate the time complexity doubles in propertion to the increase of the amount of comparisons.

Thus, the worst-case running time is still the same order as that of two way merging, but slightly large, because $\frac{2}{\lg{3}}>1$.