Здравствуйте, MTD, Вы писали:

MTD>Здравствуйте, sdf, Вы писали:

sdf>>Модифицированный quicksort трогает только часть элментов и более эффективен с точки зрения локальности и кеша.

MTD>Неплохо бы на реализацию посмотреть, потому как не понятно, что там изобретено.
Мне совершенно неохота выдирать этот алгоритм из продакшен-кода под NDA и его тут показывать, чтобы что-то вам доказывать. Я привел пример в ответ на забавную просьбу. Попробуйте решить эту задачу сами твк, чтобы решение работало быстрее, чем построение хипа из массива и последовательный вызов heap-pop N раз и чтобы оно работало эффективно, когда весь массив не умещается в памяти, вы поймете, что пространство для изобретения там есть и оно очень большое.

> Кроме того не понял, что значит "трогает только часть элментов", пройти по всем элементам придется по условию задачи.
Пройтись придется по всем, но heapsort будет хуже использовать кещ и больше переставлять элементы туда-сюда в процессе работы. На больших объёмах данных он работает заметно хуже модифицированного quicksortа