Interview-School

  1. 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 O(n) time.)
    1. nlog(n)
    2. n
    3. n^2\log(n)
    4. n(log(n))^2