Любопытное доказательство о сложности сортировки.
n - чисел. Из них можно составить n! различных наборов. Допустим, что сортируя, информацию получаем только из сравнения(Вот этот момент интересен, откуда мы её ещё можем получить? если можем, то доказательство не верно) . Значит проведя одно сравнение, мы получаем информацию 1 бит. Тоесть мы можем выбрать из 2 наборов 1 верный. Ну после k сравнений мы получим k бит информации, и сможем выбрать верный набор из 2^k наборов. Нам нужно, что бы 2^k >= n! . Тоесть k должно быть примерно равно по крайне мере log(n!) < log(n^n) = n*log(n) .
Тоесть нам надо сделать примерно n*log(n) сравнений, что бы узнать как правильно отсортировать. Как бы мы не старались, за n любых операций мы правильно не отсортируем :(