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 got this question as a homework. I know merge sort sorts in O(nlogn) time. For lexicographic order for length in is it n times nlogn ? or n^2 ?
Each comparison of the algorithm is O(n) [comparing two strings is O(n) worst case - you might detect which is "bigger" only on the last character], You have O(nlogn) comparisons in mergesort.
Thus you get O(nlogn * n) = O(n^2 * logn)