Algorithmen und Datenstrukturen · Middle · Frage 2 von 75
Was ist der Hauptnachteil von Merge Sort auf Arrays?
- 1Bei bereits sortierter Eingabe ist es O(n²)
- 2Es ist nicht stabil, gleiche Schlüssel werden umsortiert
- 3Es braucht O(n) zusätzlichen Speicher fürs Zusammenführen
Antwort zeigen
Richtige Antwort: Es braucht O(n) zusätzlichen Speicher fürs Zusammenführen
Erklärung
Der Schritt des Zusammenführens schreibt in einen temporären Puffer. Die Zeit ist unabhängig von der Eingabe O(n log n), und die klassische Umsetzung ist stabil. Auf verketteten Listen geht Merge Sort ohne zusätzlichen Puffer.