k-way-Mergesort

• Gern für Datenbanken / große Datenmengen

• Rekursiv:

  • Aufteilen in k Listen!
  • Sortieren, Zusammenmergen wie gehabt

• Laufzeit: O(n logkn) (!!)

  • logkn wächst für große k sehr langsam → „fast“ O(n):
  • log100(1000)=1,5; log100(1 Mio)=3; log100(1 Mrd)=4,5

• → k möglichst groß wählen

Notizen: