Изменения
→Среднее время работы
Лемма
|statement=Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.
|proof=Пусть <tex>ХX</tex> {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.
Переименуем элементы массива как <tex>z_1 \ldots z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1} \ldots z_j\}</tex>.
