От переводчика. Перевод статьи 2007 года на arxiv.org о статистическом анализе модификации быстрой сортировки.
Наверняка найдутся люди, использующие описанный вариант интуитивно. Здесь — математическое обоснование эффективности при n <= 7 000 000
Коротко о главном
Ключевые слова
Внутренняя сортировка; Равномерное распределение; Средняя временная сложность; Статистический анализ; Статистическая оценка
Читать полностью »