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

Computers & Technology

Justine Chavez

23 May, 14:27

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?

+1

Answers (1)

Know the Answer?

Darren Hood · 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).