Complexity analysis using 2 way merge

n strings each of size n is given what is the time taken to sort them using 2 way merge?

Habib Mohammad Khan @habibkhan
22 Sep 2016 10:00 am

First of all , lets calculate cost of merge at each level.In 2 way merge, we take 2 arrays or strings and merge.So here we will have n/2 pairs for merging separately.

Also cost of merging each pair = n+n = O(n).So overall cost of merging n/2 pairs = O(n2)

Now after merging, we will n/2 strings and hence n/4 pairs and cost of merging each pair = 2n+2n = O(n).This we will continue till we have no. of strings = 1 at the topmost level.

Hence no. of levels of the tree involved = logn

And cost of each level  = O(n2)

So overall complexity = O(n2logn) using 2 way merge