k-way merge - это алгоритм, который принимает в качестве входных данных k отсортированные массивы, каждый из которых имеет размер n. Он выводит один отсортированный массив всех элементов.

Это достигается с помощью «слияния» подпрограмма центральная в алгоритме сортировки слиянием, чтобы объединить массив 1 в массив 2, а затем массив 3 в этот объединенный массив и так далее, пока все k массивов не будут объединены.

Я думал, что этот алгоритм O (kn), потому что алгоритм перебирает каждый из k массивов (каждый длиной n) один раз. Почему это O (NK ^ 2)?