Объединить k отсортированных массивов разной длины

Question

n является степенью 2. Для каждого отсортированного массива logn-1 длиной 1,2,4,8, ..., n / 2 каждый описывается алгоритм детерминирования c для объединения их в один отсортированный массив. Я подумал, может быть, сохранить указатель на каждый из первого элемента отсортированного массива, вставить все первые элементы в двоичную кучу и удалить мин. Но тот факт, что длины разные, заставляет меня думать, что, возможно, это решение не самое лучшее.

Какой самый эффективный способ решить эту проблему?

Answer 1

Слияние самых маленьких трасс. В этом случае объедините прогоны размера {1,2}, чтобы создать прогон размера 3. Объедините прогоны размера {3,4}, чтобы создать прогон размера 7. Объедините прогоны размера {7,8}, чтобы создать прогон размер 15. ... и т. д.

Такая ситуация возникает при выполнении сортировки слиянием снизу вверх для связанных списков, в которой используется небольшой массив «списков» (указателей или ссылок на узлы), где массив [i] список размером 2 ^ i {1,2,4,8, ...}. После объединения всех узлов из списка источников в массив массив затем объединяется в один список, начиная с массива [0].

https://en.wikipedia.org/wiki/Merge_sort#Bottom -up_implementation_using_lists