Merge sort

Question

Given "log n" sorted lists each of size "n/log n",what is the total time required to merge them into one single list.

Comments

$O( n \log \log n )$

---

How
Plz tell me in detail.

---

see this

https://gateoverflow.in/784/gate2005-39?show=129329

https://www.geeksforgeeks.org/merge-k-sorted-arrays/

if still you have issue,let me know!

Answer 1

Before answering this question, Just boil down to a less easy question

Given n element, merge them into one sorted list using merge procedure.

we have n elements ,lets assume it at level 1(bottom level). Lets assume root to be at kth level.  we are merging 2 elements(each in one block)  of level 1 into single block on level 2. In this comparison & movement required it takes O(n) time. Now at level 2(second from bottom). Total number of elements will still be n But number of blocks reduced by half (if n is even it is exacty n/2. if odd then (n/2 )+1 nearly half). similarly at level 3, two of total n/2 Blocks merge together to form a single block so, at level 3 number of blocks will be (n/2)1/2 which is n/(2)^level-1= n/2².  similarly at level 4, two of total (n/2)1/2 Blocks merge together to form a single block so, at level 4 number of blocks will be ((n/2)1/2)1/2 which is n/(2)^level-1 = n/2³. So on at level k which is root number of blocks will be n/2^k-1  and we know at level k there will be only one block that is ROOT. so 

n/2^k-1 = 1

i.e. n = 2^k-1

so, log n = k -1= number of levels.=O(log n)

 

Just for movement and comparison from one level to another it takes O(n) time. So, what is total amount of time required to merge them to single list is

(Time to cross one level)*(no. Of total levels)
= n*log n

= O(n log n)

similarly, for your question,

BUT in your case, no. of total levels will be log log n so,

(Time to cross one level)*(no. Of total levels)
= n*log log n

= O(n log log n)