Rautavistische Informatik: n-way-Mergesort

• k möglichst groß wählen?

  • → wähle k=n

• Laufzeit:

  • O(n lognn)
  • =O(n × 1)
  • =O(n), also lineare Laufzeit für vergleichsbasiertes Sortieren!

Notizen: