Verwenden von mergesort merge() zum Sortieren von k geordneten Arrays

Ok, es gibt also dieses klassische Problem des "Zusammenführens von k sortierten Arrays zu einem langen sortierten Array mit merge() von mergesort". Es gibt viele Artikel und Videos darüber im Internet, die alle zu dem "Mergen Sie Arrays 2 auf 2 weiter zusammen, bis Sie nur noch eines haben. Dies dauert O(nk log k) Zeit.". Ich verstehe diese Erklärung für diesen Algorithmus und diese Zeitkomplexität.

Aber was ist, wenn die sortierten Arrays Größen haben?

$$1, 2, 4, 8, 16, ..., 2^{k}$$ ? und wir überlegen$n$jetzt ist die endgültige Array-Länge, dh, $$n = 1 + 2 + 4 + ... + 2^{k} = 2^{k+1} - 1$$ Wäre es möglich, sie alle zu einem besseren Zeitpunkt in einem einzigen Array zusammenzuführen?

Könnten Sie auch meinen Pseudocode für diesen Algorithmus auswerten:

(Betrachten Sie A als alle diese verketteten Arrays, und die Indizierung beginnt bei 1, und merge() als mergesorts merge(array, erster Index des ersten Arrays, das zusammengeführt wird, letzter Index des ersten Arrays, das zusammengeführt wird, letzter Index des letzten Arrays, das zusammengeführt wird )):

for(m = 1; m <= lg(n+1)/2; m++){
  for(i = 1; i < k/2; i = 4*i){
    merge(A, i, i*2^(m) -1, i*4^(m) -1);
  }
}

(Ich weiß, es sieht verwirrend aus, deshalb frage ich hier auch. Es tut mir leid, wenn meine Frage zu locker ist, aber jede Hilfe ist willkommen!)

(Mir sind auch die min heaps-Implementierungen bekannt, aber ich muss über diese Methode mit mergesorts merge() Bescheid wissen!)

(Danke, dass Sie bis hierhin gelesen haben!)