Некоторые способы оптимизации быстрой сортировки:

• Выбор опорного элемента. 1 В ранних реализациях, как правило, опорным выбирался первый элемент, что снижало производительность на отсортированных массивах. 1 Для улучшения эффективности может выбираться средний, случайный элемент или (для больших массивов) медиана первого, среднего и последнего элементов. 1
• Использование сортировки вставками на маленьких массивах. 13 Такие массивы можно оставлять несортированными и выполнять один этап сортировки по вставке в конце, поскольку сортировка по вставке эффективно обрабатывает почти отсортированные массивы. 3
• Отдельная сортировка вставкой каждого небольшого сегмента. 3 Это позволяет избежать напрасной траты усилий на сравнение ключей по многим границам сегмента и улучшает использование кэша. 3
• Переход на сортировку другими методами при достижении нежелательной глубины рекурсии. 1 Например, можно использовать алгоритм Introsort или некоторые реализации быстрой сортировки в библиотеке STL. 1
• Параллельная сортировка. 2 Исходный набор данных делится на две части, меньшая из которых передаётся другому свободному процессору, большая остаётся на исходном для дальнейшей обработки. 2