Сортировка массивов

[vickie_b]

Привет! У меня проблема - надо объединить 100 уже отсортированных массивов в один. Количество элементов в каждом известно. Требование (как обычно) - минимальные временные затраты. Научник настаивает на использование "пирамидальной" сортировки.
Я алгоритм этой самой сортировки нашла и в Вирте, и в Кнуте, но как приспособить его к своей задаче до меня не доходит.
Я так полагаю, что сложность должна оцениваться примерно в nlog(100) операций, n - количество элементов в итоговом массиве.
Буду благодарна за любые идеи.

[незваный гость]

Не верьте научнику! — будут тут всякие говорить, — никому не верьте! и мне тоже не верьте!:D но в данном случае он, похоже, прав.

Начнем с идеи слияния (для двух массивов). Идея проста; у нас есть дисплей (курсор), на котором светится текущий наименьший элемент массива. Сравниваем два, из того, у кого меньше, забираем, и выставляем в дисплей следующий элемент. И так до победного конца.

Для ста проходит аналогичная идея, но возникает вопрос, как искать наименьший элемент из ста. Вот тут-то и приходит на помощь куча (она же пирамида, а впросторечье heap из heapsort). Представьте себе, что мы сортируем объекты. У каждого объекта есть метод, выдающий его ключ для сортировки. Я думаю, Вам уже понятно, как построить из них кучу, правда? Теперь все просто: объект — это неиспользованная часть массива, ключ — первый неиспользованный элемент. В начале строим кучу, а вот операция разбора немного другая:

1) Из кучи берется наименьший элемент.

2) Из него выталкивается значение в итоговый массив.

3а) Остаток массива не пуст. Тогда ключ массива изменился, и мы начинаем проталкивать этот массив с вершины кучи вниз.

3б) Это был последний элемент. Поступаем, как все поступают с кучей — берем последний элемент в куче и начинаем проталкивать его вниз.

Каждый шаг в куче, действительно делается за самое большее $\log_2 100$, и все за $n \log_2 100$.

[vickie_b]

Большое спасибо за ответ. Попытаюсь реализовать.