Какая алгоритмическая сложность быстрой сортировки?

Алгоритмическая сложность быстрой сортировки (quicksort) — O(n log n) в среднем и лучшем случае, O(n²) в худшем. По памяти — O(log n).

Временная сложность

Средний и лучший случай: O(n log n)

Quicksort делит массив на части вокруг опорного элемента (pivot) и рекурсивно сортирует их:

• log n уровней рекурсии (деление пополам).
• n операций на каждом уровне (разбиение).
• Итого O(n log n).

Худший случай: O(n²)

Когда pivot выбирается неудачно (например, всегда минимум/максимум на отсортированном массиве) — разбиение крайне несбалансированное:

[1,2,3,4,5], pivot всегда первый → n уровней по n операций → O(n²)

Хороший выбор pivot (случайный, медиана трёх) делает худший случай маловероятным.

Пространственная сложность: O(log n)

Quicksort сортирует на месте (in-place), доп. память — только на стек рекурсии: O(log n) в среднем, O(n) в худшем.

Особенности

• In-place — не требует много доп. памяти (плюс перед merge sort O(n)).
• Нестабильная — может менять порядок равных элементов.
• Быстрая на практике — хорошие константы, кеш-дружелюбна.

Quicksort против merge sort

• Quicksort — O(n log n) в среднем, O(n²) худший, in-place, нестабильная.
• Merge sort — O(n log n) всегда (гарантия), но O(n) памяти, стабильная.

Коротко для собеседования

Quicksort: O(n log n) в среднем и лучшем случае (деление вокруг pivot), O(n²) в худшем (неудачный pivot на отсортированных данных — решается случайным pivot). Память O(log n) — сортирует in-place, нестабильная. На практике быстра. Merge sort даёт гарантированный O(n log n), но требует O(n) памяти.