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

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

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

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

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