Number of List = Log(n) , Number of elements in each list = n/Log(n)
Take the pair appraoch( like merge in pairs , (1,2) is first pair , (3,4) is the second pair , (4,5) , (6,7)...... (log(n) - 1,logn) will be the log(n)/2 th pair and merge using merge procedure of mergesort which takes Theta(k) where k is the number of elements in big one list.
Thus for first attempt the work will be [ ( n/log(n) ) * ( log(n)/2 ) ]= n/2 as theta(n/log(n)) work has to be done for each pair and total log(n)/2 pairs are there
Second attempt , as now we have ( log(n)/2 ) list so again make pairs but now element in each list is 2n/log(n)
thus work will be => ( 2n/logn) * (log(n)/4 ) = n/2
similliarly again number of list will be half then make pairs thus for third attempt work will
be = (4n/logn) * (log(n)/8) = n/2
and so on....
total log(logn) attempt will be there , after that we will get single list of n elements
Thus (n/2 + n/2 + n/2 + ....... log(logn) terms )
thus ans = (n/2)* ( log(logn) ) = n log(logn)