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