|
|
|
|
|
|
by maweki
3454 days ago
|
|
|
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). |
|
|