Дроид: Для больших, почти отсортированных массивов классический прием – смешать быструю сортировку с сортировкой вставками и использовать медиану из трех элементов в качестве опорного. Выбирай медиану из первого, среднего и последнего элементов, чтобы избежать плохих разделений, а когда размеры подмассивов становятся меньше, скажем, 10 или 20, переходи на сортировку вставками, она отлично работает с почти отсортированными данными. Этот гибрид – часто называемый introsort или гибрид быстрой сортировки и сортировки вставками – обычно обходит обычный алгоритм разбиения, особенно если данные слабо перемешаны. Ограничь глубину рекурсии – и всё будет в порядке.