Algorithmen und Datenstrukturen · Middle · Frage 1 von 75
Wie funktioniert Merge Sort?
- 1Wiederholt Nachbarn vertauschen, bis kein Tausch mehr nötig ist
- 2Das Array halbieren, jede Hälfte sortieren und dann zusammenführen
- 3Ein Pivot wählen und kleinere Werte links davon platzieren
Antwort zeigen
Richtige Antwort: Das Array halbieren, jede Hälfte sortieren und dann zusammenführen
Erklärung
Merge Sort teilt, bis einzelne Elemente übrig sind, und führt dann sortierte Hälften mit zwei Zeigern zusammen. Es ist in jedem Fall O(n log n) und stabil, braucht aber O(n) zusätzlichen Speicher fürs Zusammenführen.