Сравнение Сортировка Алгоритм Сложность

Question

Почему нижняя граница временной сложности алгоритмов сортировки на основе сравнения O (n log n)?

Answer 1

http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

отвечает на этот вопрос достаточно хорошо, я думаю.

Answer 2

Одним словом, потому что вы должны смотреть на каждый элемент, который является O (n). Для каждого из этих элементов, на которые вы смотрите, вы должны выяснить, находится ли он в правильном порядке, что в лучшем случае O (log n) (например, двоичный поиск). Таким образом, чистая сумма становится O (n log n)