# 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))$.

• I have mentioned that we have n strings of n length, so t = n and txn = nxn = n^2. – Navjot Singh Aug 8 '18 at 12:08
• Right, but what happens after say $\frac{1}{2}log(n)$ recursive calls? you have $\sqrt n$ strings of size $n$ so the merge step should take $O(\sqrt n \cdot n)$ and not $O(\sqrt n^2)=O(n)$ as your formula suggests. – dave Aug 8 '18 at 12:17
• @JotWaraich The problem is that $n$ changes in the recursive calls, but the string length doesn't. E.g. think about the first recursive step. You have $n/2$ strings to sort, so the merge step will only take $n \cdot n/2$. However in your recursion it would take $(n/2)^2$. So you cannot use the same variable for different things. As dave said, use $t$ in your recursion, or $m$, and afterwards replace $t = n$. – Jakube Aug 8 '18 at 12:18
• @JotWaraich I called the input size $m$ (we usually want to compute the running time of an algorithm as a function of the input size). Often we use $n$ to denote the input size, but in this case n is used to denote the number of strings and the input size is $n^2$. So I've used another letter to denote the input size, i.e. $m=n^2$. – dave Aug 8 '18 at 12:48