Какие существуют способы оптимизации быстрой сортировки?

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

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