Кто первым доказал, что вся сортировка на основе сравнения - это Омега (n lg n)?

Question

Кто первым доказал, что вся сортировка на основе сравнения - это, по крайней мере, Omega (n lg n)? Есть ли имя, прикрепленное к этому нижнему пределу? например Теорема SomeGuysLastName?

Answer 1

Моя копия «Введение в алгоритмы» имеет это, чтобы сказать в примечаниях к главе 8, где обсуждается эта граница:

Модель дерева решений для изучения видов сравнения была введена Фордом и Джонсоном (1). Комплексный трактат Кнута по сортировке (2) охватывает многие вариации проблемы сортировки, включая теоретико-информационную нижнюю оценку сложности сортировки, приведенную здесь.

(1) Лестер Р. Форд-младший и Сельмер М. Джонсон. Задача турнира. Американский математический ежемесячник , 66: 387-389, 1959.

(2) Дональд Э. Кнут. Сортировка и поиск , том 3 из Искусство компьютерного программирования . Аддисон-Уэсли, 1973.

Не однозначный ответ на ваш вопрос, но это что-то.

Answer 2

Сортировка слиянием (наихудший сценарий: n log n) была изобретена Джоном фон Нейманом в 1945 году, поэтому я думаю, что он был первым, кто это доказал.

Но, может быть, грек доказал это в 400 г. до н.э., действительно ли это имеет значение?

http://en.wikipedia.org/wiki/Merge_sort