Кратко: при выборе опорного элемента как $A[(l+r)/2]$ и при большом числе одинаковых элементов стандартная реализация разбиения часто не удаляет эти равные элементы из дальнейших рекурсий, поэтому каждая рекурсия обрабатывает почти тот же массив — получается рекуррентное соотношение типа
$$T(n)=T(n-1)+O(n)\Rightarrow T(n)=O(n^2),$$ то есть квадратичное время. Причина — неудачная обработка элементов, равных pivot, и/или постоянное получение «небалансных» разбиений.
Варианты исправления и их оценка:
1) Трёхдольное (Dutch national flag) разбиение: разделить на три части «меньше», «равно», «больше» и рекурсивно сортировать только «меньше» и «больше». При многих одинаковых элементах это даёт один проход $O(n)$ и никаких дальнейших рекурсий (для всех равных — общая сложность $O(n)$). В общем среднем случае — $O(n\log n)$, в худшем теоретическом (при постоянном плохом pivot) — $O(n^2)$.
2) Случайный выбор pivot или предварительная случайная перестановка массива: уменьшает вероятность неблагоприятных последовательностей; ожидаемое время $O(n\log n)$, худший случай по-прежнему $O(n^2)$ (но с очень малой вероятностью).
3) Median-of-three (медиана из первого, среднего, последнего): обычно улучшает баланс разбиений на «реальных» данных, ожидаемое $O(n\log n)$, худший — $O(n^2)$.
4) Introsort (комбинация quicksort + heapsort при глубине рекурсии > $c\log n$): обеспечивает гарантированное худшее время $O(n\log n)$ и среднее $O(n\log n)$; дополнительная сложность реализации невелика, память — константная/стек $O(\log n)$.
5) Выбор медианы с помощью алгоритма median-of-medians для pivot: гарантированно даёт сбалансированные разбиения, итоговое время $O(n\log n)$ в худшем случае, но с большим константным множителем (дорого в практике).
Альтернатива: если важен детерминированный худший случай и/или стабильность, использовать mergesort ($O(n\log n)$ худшее, но требует $O(n)$ доп. памяти) или heapsort ($O(n\log n)$ худшее, in-place).
Рекомендация на практике: для массивов с большим числом одинаковых элементов — реализовать трёхдольное разбиение (или использовать реализацию std::sort / qsort с 3-way/Bentley–McIlroy) и/или случайную перестановку; для гарантий по худшему случаю — introsort.