Merge sort worst case running time for lexicographical sorting? A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge step would be $O(n^2)$. So the recurrence should be of the form


  $$T(n) = 2T(\frac n2) + O(n^2)$$


By master's theorem it solves to $O(n^2)$.

Somehow some people on the internet claim the following explanation:
Merge sort makes $O(nlogn)$ comparisons and since it is lexicographical sort each comparison take $O(n)$ time, so worst case time is $O(n^2logn)$.

Which of the above is correct and if at some point i am incorrect please correct me.
The recurrence formula is incorrect. 

Lets say you have $t$ strings, so the running time of merge isn't $O(t^2)$ but $O(t\cdot n)$.

Change variables: the input size is $m=n^2$, and the recurrence formula should be

$$T(m)=2 T\left( m/2 \right) + O(m) $$ 

So you get $T(m)=O(m\log(m))$ and therefore $T(n^2)=O(n^2\log(n))$.