k-way merge to algorytm, który przyjmuje jako wejściowe k posortowane tablice, każda o rozmiarze n. Wyprowadza jedną posortowaną tablicę wszystkich elementów.

Robi to za pomocą procedury „scalania” centralnej dla algorytmu sortowania scalającego, aby scalić tablicę 1 z tablicą 2, a następnie tablicę 3 z tą scaloną tablicą, i tak dalej, aż wszystkie k macierze zostaną scalone.

Myślałem, że ten algorytm to O (kn), ponieważ algorytm przemierza każdą z tablic k (każda o długości n) raz. Dlaczego jest to O (nk ^ 2)?