Изменения

|statement=Если алгоритм сортировки является рандомизированнымНе существует структуры данных, то для него справедливо, что нижняя граница матожидания времени работы для сортировки сравнениями которая поддерживает добавление элементов и извлечение минимума за амортизированное время <tex> O(1) </tex>. Даже если остальные операции могут выполняться сколько угодно долго.|proof=Верхние границы <tex>O(n \log n) </tex> элементов равна времени работы пирамидальной сортировки и сортировки слиянием совпадают с нижней границей <tex> \Omega(n \log n) </tex>для наихудшего случая из теоремы о нижней границе для сортировки сравнениями.