How Fast Can We Sort?
The most basic sorting algorithms, such as Bubble Sort, run in time. Some more complicated ones, like Merge Sort, improve dramatically to time. Is it possible to create a sorting algorithm with worst-case runtime
Bonus: If "yes", can you name one and/or create one? If "no", why not?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
If we consider the (binary) results of comparisons performed by any sorting algorithm, it is in one-to-one correspondence with the input string. There are n ! possible input strings and hence it would require at least lo g ( n ! ) = O ( n lo g n ) comparisons for correctly sorting any input string by any sorting algorithm.