Слияние отсортированных массивов, какова оптимальная временная сложность?

Question

У меня есть m массивов, каждый массив имеет длину n.Каждый массив отсортирован.Я хочу создать один массив длиной m * n, содержащий все значения предыдущих массивов (включая повторяющиеся значения), отсортированные.Я должен объединить эти массивы ..

Я думаю, что оптимальная временная сложность составляет m * n * log (m)

Вот эскиз алгоритма ..

Iсоздайте вспомогательный массив H длины m, содержащий все значения первого элемента каждого массива.

Затем я сортирую этот массив (m log m) и перемещаю значение min в выходной массив.

Затем я заменяю перемещенное значение на следующее из массива, в котором оно было взято.На самом деле я не заменяю его, но вставляю в правильное (отсортированное) положение.Я думаю, что это займет m m.

И я повторяю это для всех значений m * n ... поэтому m * n * log m

Мой вопрос .. Вы можете придумать более эффективныйалгоритм?Если mnlogm действительно оптимален, можете ли вы хотя бы придумать более простой и элегантный алгоритм?

Answer 1

Сложность правильная!Однако в вашей идее алгоритма есть небольшой недостаток: вы не можете вставить элемент в отсортированный массив в log m.Вы можете найти его положение с помощью бинарного поиска в этой сложности, но вам, возможно, придется перемещать элементы, чтобы фактически разместить его там.Чтобы решить эту проблему, вы можете вместо этого использовать кучную структуру данных!

Многофакторное слияние (которое является общим названием вашего алгоритма) обычно реализуется с помощью еще одной «объединяющей» структуры данных: турнир-tree.Вы можете найти описание в «Искусстве компьютерного программирования» Кнута (глава по сортировке, iirc).Он имеет более низкий постоянный коэффициент в теории и на практике по сравнению с кучами в этом конкретном случае.

Если вы хотите посмотреть реализации, я почти уверен, что параллельное многоканальное слияние в стандарте GNU C ++библиотека параллельных расширений реализована следующим образом.

Редактировать: Я ссылался не на ту книгу, которая сейчас исправлена.

Answer 2

Лучшее, что вы можете сделать, это O (m * n + d). Аналогично подсчету сортировки: http://en.wikipedia.org/wiki/Counting_sort Если вы знаете диапазон возможных значений (скажем, d), вы можете инициализировать массив длины d, а затем просмотреть каждый из m массивов, добавив 1 к каждому «бену» d для каждого значения, соответствующего этому бин. Затем в вашем новом массиве длины m * n для каждого значения в d вы добавляете сколько угодно значений, которые имеет bin.