Why is sorting a string O(n log n)?

Question

Possible Duplicate:
Plain English explanation of Big O

In the answer to a programming puzzle it said sorting a string takes O(n log n) time. How is that derived?

Does anybody have a good reference link for Big O resources.

Thanks

Answer 1

Why is sorting a string O(n log n)?

Sorting the characters in a string is not necessarily O(n log n).

• O(n log n) is the optimal value for a comparison sort. It is also the complexity of many languages' default sort implementation. However it's certainly possible to do worse than this. The complexity of sorting the characters in a string depends on the specific algorithm you choose to solve this task.
• It's also possible to do better than O(n log n) in some cases by using a sorting algorithm which is not a comparison sort. For example, if you know that you have an ASCII string with a maximum of 127 distinct characters you could use a counting sort which is O(n). A counting sort would also be feasible for Unicode strings where all characters are in in the Basic Multilingual Plane.

Answer 2

A definition and some examples of Big O can be found by using a search engine, e.g. here:

• http://en.wikipedia.org/wiki/Big_O_notation

An explanation of sort algorithms based on comparing elements, together with an explanation for the lower bound on the number of required comparisons, can be found here:

• http://en.wikipedia.org/wiki/Comparison_sort