O k-way merge é o algoritmo que toma como entrada k ordenadas matrizes, cada uma do tamanho n. Ele gera uma única matriz ordenada de todos os elementos.

Ele faz isso usando a rotina de "mesclagem" central para o algoritmo de classificação de mesclagem para mesclar o array 1 ao array 2 e, em seguida, o array 3 para esse array mesclado, e assim por diante até que todos os k arrays tenham mesclado.

Eu tinha pensado que este algoritmo é O (kn) porque o algoritmo atravessa cada um dos k arrays (cada um com comprimento n) uma vez. Por que é O (nk ^ 2)?