k-way merge ist der Algorithmus, der k sortierte Arrays der Größe n als Eingabe verwendet. Es gibt ein einzelnes sortiertes Array aller Elemente aus.

Dazu wird die "Merge" -Routine verwendet, die für den Merge-Sortieralgorithmus von zentraler Bedeutung ist, um Array 1 mit Array 2 und anschließend Array 3 mit diesem zusammengeführten Array zusammenzuführen, usw., bis alle k Arrays zusammengeführt wurden.

Ich hatte gedacht, dass dieser Algorithmus O (kn) ist, weil der Algorithmus jedes der k Arrays (jedes der Länge n) einmal durchläuft. Warum ist es O (nk ^ 2)?