Question

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?

Answer 1

O(N log_3 N), as opposed to O(N log_2 N).

Fewer recursive calls (smaller tree depth), but the trade-off is added complexity, especially in the merging routine (big O notation is hiding larger coefficients).