Быстрая сортировка median-of-three работает заметно лучше, чем рандомизированная быстрая сортировка?

Я как раз отвечал на вопрос о различных подходах к выбору раздела в реализации быстрой сортировки и задал вопрос, на который я, честно говоря, не знаю, как ответить. Это немного усложнено математикой, и это может быть неправильный сайт, на котором можно задавать такие вопросы, поэтому, если это нужно перенести, сообщите мне, и я с радостью перенесу его в другое место.

Это ' Хорошо известно, что реализация быстрой сортировки, которая выбирает свои опорные точки равномерно случайным образом, в конечном итоге будет запущена в ожидаемое время O (n lg n) (есть хорошее доказательство этого в Википедии ). Однако из-за затрат на генерацию случайных чисел многие реализации быстрой сортировки не выбирают опорные точки случайным образом, а вместо этого полагаются на подход «медиана из трех», в котором три элемента выбираются детерминированно и из которых медиана выбирается в качестве стержень. Известно, что это вырождается в O (n ² ) в худшем случае (см. эту замечательную статью о том, как сгенерировать эти входные данные для худшего случая, например).

Теперь предположим, что мы объединить эти два подхода, выбирая три случайных элементов из последовательности и с использованием их медиана как выбор поворота. Я знаю, что это также гарантирует время выполнения в среднем случае O (n lg n) с использованием немного другого доказательства, чем для обычной рандомизированной быстрой сортировки. Однако я понятия не имею, что такое постоянный множитель перед членом n lg n в этой конкретной реализации быстрой сортировки. Для регулярной рандомизированной быстрой сортировки Википедия перечисляет фактическое время выполнения рандомизированной быстрой сортировки как требующее не более 1,39 n lg n сравнений (с использованием lg в качестве двоичного логарифма).

Мой вопрос: знает ли кто-нибудь способ получить постоянный коэффициент для количества сравнений, сделанных с использованием рандомизированной быстрой сортировки "медиана из трех" ? Если мы пойдем еще шире, есть ли выражение для постоянного множителя при быстрой сортировке с использованием подхода рандомизированной медианы k? Мне любопытно, потому что я думаю, было бы интересно посмотреть, есть ли такие "

Большинство модификаторов имеют для меня смысл - абстрактные, защищенные и т. Д. Но «виртуальный» кажется сбивающим с толку произвольным выбором того, что действительно «переопределяется».

' «Виртуальный» в вычислениях (виртуальная машина, виртуальная память), кажется, означает абстрактное представление чего-либо. Я предполагаю, что это произошло из оптики, где виртуальное изображение (обычно в * vert * ed) происходит от средневекового латинского virtuālis, что означает «эффективный».

Так что мне кажется, что это имело бы больше смысла если бы «виртуальный» метод в вычислениях был преобладающим, а не подлежащим отмене.

Может быть, я упускаю что-то фундаментальное о " virtual ', может ли кто-нибудь пролить свет на то, почему он был выбран?