Merge-sort a string

Computer Science Level 2

Given a list of $n$ strings each of length $n$ . What will be the worst case running time of sorting the strings in lexicographic order using merge-sort algorithm?

O(n^{2}\log n)

O(n^{2})

O(n\log n)

O(2^{n}\log n)

2 solutions

Christopher Boo
May 15, 2016

Merge Sort needs $O(n\lg n)$ comparisons to sort $n$ objects. To compare two strings of length $n$ in lexicographic order, we compare the characters one-by-one until one where both are different. The worst case of this is $O(n)$ where every characters are the same. Hence, $O(n\lg n)$ comparisons and each comparisons need $O(n)$ , the answer is $O(n^2\lg n)$ .

But we can simply compare two strings using relational operators then, for comparison it would cost O(1).

201951003 ABHIJEET TAMRAKAR - 9 months ago

Georgi Lyubenov
Mar 7, 2016

Why level 3? Lexicographically = letter by letter, so if every string is of length n then at worst you would have to compare n times.

Merge-sort a string

2 solutions

0 pending reports