Aufgabe mit Lösung Mergesort-Algorithmus
Führe Mergesort-Algorithmus mit dem folgenden Array durch und gib dabei nach jedem Schritt die Teilarrays an:
[14, 33, 12, 45, 42, 51, 89, 63, 80, 35]
Lösungstipps
- Array in der Mitte aufteilen
- Teilarrays in der richtigen Reihenfolge zusammenfügen
Lösung
Als erstes wird das Array in der Mitte aufteilt:
[14, 33, 12, 45, 42] [51, 89, 63, 80, 35]
Die beien Teilarrays werden jeweils in der Mitte aufgeteilt. Da die Anzahl der Elemente in beiden Arrays ungerade ist, wird die Aufteilung abgerundet (5/2 ~ 2):
[14, 33, 12, 45, 42] [51, 89, 63, 80, 35]
[14, 33][12, 45, 42][51, 89][63, 80, 35]
Die vier entstandenen Teilarrays werden analog aufgeteilt:
[14, 33, 12, 45, 42] [51, 89, 63, 80, 35]
[14, 33][12, 45, 42][51, 89][63, 80, 35]
[14][33][12][45, 42][51][89][63][80, 35]
Die Arrays, die noch nicht einelementig sind, werden weiter aufgeteilt:
[14, 33, 12, 45, 42] [51, 89, 63, 80, 35]
[14, 33][12, 45, 42][51, 89][63, 80, 35]
[14][33][12][45, 42][51][89][63][80, 35]
[14][33][12][45][42][51][89][63][80][35]
Anschließend müssen die einelementigen Arrays in der richtigen Reihenfolge (von klein nach groß) zusammengefügt werden. Zuerst werden die zuletzt aufgespaltenen Arrays wieder zusammengefügt:
[14, 33, 12, 45, 42] [51, 89, 63, 80, 35]
[14, 33][12, 45, 42][51, 89][63, 80, 35]
[14][33][12][45, 42][51][89][63][80, 35]
[14][33][12][42, 45][51][89][63][35, 80]
[14, 33][12, 42, 45][51, 89][35, 63, 80]
[12, 14, 33, 42, 45][35, 51, 63, 80, 89]
[12, 14, 33, 35, 42, 45, 51, 63, 80, 89]
