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

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

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

Вот набросок алгоритма ..

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

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

Затем я заменяю перемещенное значение следующим из массива, которое оно было взято. Собственно не заменяю, а вставляю в нужную (отсортированную) позицию. Думаю, это займет log m.

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

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