Прочитал я всю эту дискуссию (ну не всю — терпения не хватило и вот какой вопрос хочу задать.

Линейной сортировка вроде бы быть не может, кажется, где-то я видел доказательство этого.

Можно ли доказать, что лучше O(nlog(n)) быть не может ?