Sorting n strings using Merge sort

Question

A list of n strings each of length n is sorted into lexicographic order using the merge sort algorithm. The worst case running time of this computation is?

I searched this question and everywhere I found the answer to be: O(n²logn).

While my approach is as follows:
Comparing two strings require O(n) comparisons, hence each merge will take O(n²) time.
So, the recurrence equation will be:
T(n) = 2T(n/2) + O(n²)
Therefore, by Master Method:
T(n) = O(n²).

Correct me where I am wrong.

Answer 1

Your analysis and reduction is correct. But the problem is in the interpretation of recurrence equation of master theorem.

T(n) = 2T(n/2) + O(n²)

The n in the equation represents no.of elements in the list to be sorted. The O(n²) is not entirely correct. It is O(n * n-character comparisons). This will be evident if we substitute 'n-character comparisons' operations with a different complexity, which is independent of no.of elements. Let it be O(m). Then we have

T(n) = 2T(n/2) + O(n * m)

we have a = 2, b = 2, c = 1 and c = Log_ba (case 2)

Hence, T(n) = O(n * m * log n)

Now, substituting m with n

T(n) = O(n² * log n)

We can also justify this as - the recurrence tree for merge sort will have height Log(n). O(n²) work will be done at each level of the recurrence tree in merge operation.

Hence, a total of O (n² log n)

Hope it helps!

Answer 2

I think that your conclusion of O(n^2*lgn) is correct. If you were dealing with a set of n numbers, we know that mergesort would require O(nlgn). The difference here is that we are now dealing with strings, each of which is n long. The only impact on the mergesort algorithm would be the comparison of two strings in the base case. Instead of an O(1) comparison of two numbers, we would instead have to compare the two strings. In the general case, this is an O(n) operation, because we might have to walk down each of the two length n strings.