Создать алгоритм сортировки

[werd]

Дано:
массив длиной $n$ .место каждого члена равно меньше $k$ от того места где тот член должен быть в сортированном массиве.
Требуется предложить алгоритм который справляется с задачей сортировки в $O(n logk)$.

Кто может дать подсказку пути решения?

[Null]

Можно сделать пирамидальную сортировку с пирамидой размера $3k$

[ИСН]

Тупо берём k верхних. (Где-то среди них настоящий верхний.) Их честно сортируем. Один выставляем. Ещё один берём и вставляем...

[Null]

Вставка $O(k)$. Или в чем хранить предлагаете.

[Dandan]

вставка в отсортированный кусок из $k$ элементов будет происходить за $O(logk)$

[Null]

Как?

[Dandan]

с помощью сортирующего дерева http://ru.wikipedia.org/wiki/%D0%A1%D0% ... 0%B2%D0%BE. Которое, кстати, как раз и используется в пирамидальной сортировке.

[Null]

Ну тогда он не от сортированный получается а как я сказал пирамида(двоичная куча)

[Dandan]

в начале мы создаем кучу из верхних k элементов. На каждом шаге мы будем извлекать максимальный элемент из кучи и вставлять новый. В конце из извелеченных максимальных у нас получится массив, а не куча.

[Null]

Мы говорим про кусок из k элементов он не отсортированный, он куча.