GATE CS 2012 Q39 — Searching, Sorting, Hashing

To find the worst-case running time of sorting $n$ strings, each of length $n$, using merge-sort, we analyze the two main operations performed during the algorithm: string comparisons and string copying.

1. Comparison Cost:

• Standard merge-sort on $n$ elements requires $O(n \log n)$ comparisons in the worst case.
• Comparing two strings of length $n$ lexicographically takes $O(n)$ time in the worst case (since we may need to compare up to all $n$ characters).
• Therefore, the total time spent on comparisons is:
  $$\text{Comparison Time} = O(n \log n) \times O(n) = O(n^2 \log n)$$

2. Copying Cost:

• At each of the $\log n$ levels of the merge-sort recursion tree, all $n$ strings are copied into auxiliary arrays during the merge step.
• Copying a single string of length $n$ takes $O(n)$ time.
• Thus, the copying cost at each level is $O(n \times n) = O(n^2)$.
• Across all $\log n$ levels, the total copying time is:
  $$\text{Copying Time} = O(n^2) \times \log n = O(n^2 \log n)$$

Combining both costs, the overall worst-case running time is $O(n^2 \log n)$.

Hence, the correct option is (B).