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?

Question

Aaron Sims

Computers & Technology

30 July, 06:22

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?

+3

Answers (1)

Know the Answer?

Nickolas Church · 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).