This question already has an answer here:

I saw this question and tried to find out what the time complexity was:

Using the recurrence relation for Merge Sort:

$$T(n)\; =\; merge\_time\; +\; 2T(n/2)$$

Here, since we have a list of strings, the relevant merge operation is that of merging two sorted arrays of strings. Since comparing two strings is itself a $O(n)$ operation, this takes $O(n^2)$. Thus:

$$T(n)\; =\; O(n^2)\; +\; 2T(n/2)$$

Solving this, gives $O(n^2)$, not $O(n^2logn)$. This seems to suggest that this sorting can be done within quadratic time for all inputs. However, in this answer, it is explained why this is not the case. So, can somebody tell me what I am doing wrong here?


marked as duplicate by Community Dec 13 '18 at 12:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.