Быстрая сортировка какая сложность?

а мне на собесе только спросили худший случай, средний даже не заикнулись, видимо не все спрашивают одно и то же

O(n log n) в среднем, O(n²) в худшем случае, это ответ, если нужен только один. Дальше суть. Быстрая сортировка берёт опорный элемент, расставляет всё что меньше слева, что больше справа, и рекурсивно повторяет то же самое для каждой половины. Когда опорный делит массив примерно пополам, глубина рекурсии, логарифм от n, а на каждом уровне суммарно проходишь n элементов, отсюда n log n. Но если тебе не повезло с выбором опоры, например, всегда берёшь первый элемент, а массив уже отсортирован или почти отсортирован, деление получается кривое: один кусок почти пустой, второй почти весь массив целиком. Уровней рекурсии становится n вместо log n, и получается уже n умножить на n, то есть квадрат. Возьми для примера массив из пяти чисел: 5, 4, 3, 2, 1. Если всегда брать первый элемент как опору, каждый раз будешь откалывать по одному числу, и сравнений понадобится почти как при пузырьковой сортировке. Отсюда практический вывод: опору лучше выбирать случайно или как медиану трёх элементов, тогда шанс наткнуться на такой плохой случай крайне маленький, почти нулевой на практике. Сравни с сортировкой слиянием: там гарантия n log n всегда, без всяких оговорок про худший случай, но она требует дополнительной памяти под копии массива. Быстрая сортировка сортирует на месте, поэтому её и любят разработчики стандартных библиотек, просто добавляют защиту от плохого выбора опоры.