Сортировка n-нарной пирамидой

[GCU]

Число потомков хорошо подобрать по размеру кеш линии, которая для x86 64 байта. Соответственно если сравнивать просто 32битные ключи, то n=16. Для 64х битных уже 8. Простые сравнения чисел намного быстрее промахов кэша.

[OasisInDesert]

Отличный материал. Не пожалел времени на чтение.

[kovserg]

Мне больше нравиться название метод «царь горы» оно сразу объясняет как это работает. А вот слово «просейка» — как-то мало информативно.

[valemak]

Царь горы — максимум в корне — это уже конечный результат многократной просейки. А единичная просейка не столько направлена на поднятие максимума вверх, сколько на то, чтобы скинуть мелочь как можно ниже.

[Videoman]

N-арный heapsort будет обгонять простой heapsort, если стоимость операций:
взять соседний элемент на том же уровне N или взять на уровне выше/ниже (N±1) будет разной. Например если дерево на диске, а соседние элементы лежат физически в одном блоке. Тогда чем выше N, тем более быстрорастущим будет дерево и тем больше будет скорость сортировки. Здесь полная аналогия с бинарным и B-деревом.