Median of medians подход очень популярен вquicksort Используйте алгоритмы разделения типов, чтобы получить довольно хороший поворот, чтобы он равномерно разделял массив. Его логика дана в Википедии как:

Выбранная опорная точка является как меньшей, так и большей, чем половина элементов в списке медиан, что составляет около n / 10 элементов (1/2 * (n / 5)) для каждой половины. Каждый из этих элементов имеет медиану 5, что делает его меньше, чем 2 других элемента и больше, чем 2 других элемента вне блока. Следовательно, опорная точка составляет менее 3 (n / 10) элементов вне блока и больше, чем другие 3 (n / 10) элементов вне блока. Таким образом, выбранная медиана разделяет элементы где-то между 30% / 70% и 70% / 30%, что обеспечивает линейное поведение алгоритма в худшем случае.

Может ли кто-нибудь объяснить это немного доходчиво для меня. Мне трудно понять логику.