k-way merge es el algoritmo que toma como entrada k arreglos ordenados, cada uno de tamaño n. Da salida a una sola matriz ordenada de todos los elementos.

Lo hace usando la rutina "fusionar" central para el algoritmo de ordenamiento de fusión para fusionar la matriz 1 a la matriz 2, y luego la matriz 3 a esta matriz fusionada, y así sucesivamente hasta que todas las k matrices se hayan fusionado.

Pensé que este algoritmo es O (kn) porque el algoritmo atraviesa cada uno de los k arreglos (cada uno de longitud n) una vez. ¿Por qué es O (nk ^ 2)?