CODEWITHSUNDEEP
sortingtime-complexity
JavaDeveloper
JavaDeveloper

Reputation: 5660

Complexity of sorting a string array

Assume we have an string array str = ["foo", "bar", "zebras", "topper"] which I need to to sort to get ["bar", "foo", "zebra", "top"], the sorting complexity will be O(nlogn) where n is the length of the array. But we also do string compare, which should be O(m) where m is the length of longest strings (such as zebras and topper). So final complexity should be O(m * nlogn). Please correct me if I am wrong.

This question differs from here because, here I am comparing all strings with all strings, rather than a fixed string with just one.

Upvotes: 4

Views: 5891

Answers (1)

Chris Jefferson
Chris Jefferson

Reputation: 7157

This is the result you would get if you performed sort using only normal string comparison.

You can get better performance (but I don't now of any implementations of this) by knowing your inputs are strings. For example, if you sort the strings by each character in turn, which gives O(nm|alphabet|).

Upvotes: 2

Related Questions