Стабильная сортировка сравнением с O(n *log(n))времени и O(1)пространственной сложностью

Просматривая список алгоритмов сортировки в Википедии я заметил, что не существует стабильной сортировки сравнением , которая имеетO(n*log(n))(наихудший-случай)время-сложность иO(1)(наихудший-случай)пространственная-сложность. Это, безусловно, похоже на теоретическую границу, но я не смог найти больше информации об этом.

Как можно это доказать?

Примечание:Я знаю о нижнем пределе O(n*log(n))наихудшего-времени-сложности для сравнительных сортировок.

6
задан Florian Brucker 19 March 2012 в 20:37
поделиться