Работает ли быстрая сортировка с рандомизированным средним из трех заметно лучше, чем рандомизированная быстрая сортировка?

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

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

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

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

Спасибо