Re:Writing a Faster Sorting Algorithm
by maweki on Tuesday January 03, 2017 @09:34AM
(#13309342)
You only ever have to move every element once to get a (pre-known) permutation that represents the sorted list.
The problem is the information in a permutation (n! possible orderings) and one can only ever "throw away" half of them on every comparison, leading to log_2(n!) or nlog(n).
The problem is the information in a permutation (n! possible orderings) and one can only ever "throw away" half of them on every comparison, leading to log_2(n!) or nlog(n).