here , In order to sort the strings we are follow lexicographically order / Dictionary Order ,
ie: if i have two strings aab and aaa, how to compare them is ist we have to compare the ist letter of the string which is (a and a) they are same ,
then 2nd letter a and a they are same , then compare 3rd letter from strings which is a and b .
therefore aaa is lesser then aab , therefore this "aaa" has to come in the beginning ,
so that is the comparison has to be done .
Now if the ist string is having "n " length and the 2nd string having "n" length
then , how much time will it take to compare is = actually we do characters wise comparing
therefore , for one comparison the Time complexity = O(n)
Now , there are "n" Strings and the size of each String is "n" .
Now , As we do 2-way merging , we take 2 strings and compare them and merge the 2 elements into a lexicographically order
therefore , no of comparison are going to be = O$(\frac{n}{2})$ = O(n)
and every comparison is going to take : O(n)
therefore , it's going to take : O(n2) in order to compare
As we know total size of the list = (each string have "n" characters) * ( total "n" strings are there ) = n2
now ,we have to copy all of the elements in the next level which require = O(n2)
therefore, time taken for comparing + time taken to copy all the element = so total time taken in one level = O(n2) + O(n2) = O(n2)
therefore , for every level : O(n2) work is done .
then number of levels are there = O( log (n) ) levels
and each level require : O(n2)
therefore , total work done = O( n2 log(n) )