Mergesort rekursive array sortieren

Question

Folgendes Array soll rekusive gelöst werden  array = { 9 1 7 3 8 2 6 4 }. Wie würde das Array nach jedem Merge-Schritt aussehen.

Meine Lösung:

{ 9 1 7 3 8 2 4 6}, {9 1 7 3 2 8 4 6}, {9 1 3 7 2 8 4 6}, {1 9 3 7 2 8 4 6}, { 1 9 3 7 2 4 6 8}, { 1 3 7 9 2 4 6 8}, { 1 2 3 4 5 6 7 8 9}

Für mich ist hier nur wichtig, dass ich verstehe, in welcher Reihenfolge vorgegangen wird. Wenn ich die Teilprobleme rekursive löse, sollten meine Zwischenergebnisse stimmen.

LG

Answer 1

Für mich ist hier nur wichtig, dass ich verstehe, in welcher Reihenfolge vorgegangen wird.

Lasse Dir dafür die einzelnen Steps am besten einmal mit diesem Tool anzeigen:

https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/

Comments

Hab es jetzt handschriftlich noch ein mal gemacht. Sollte wohl so aussehen:

{ 1 9 7 3 8 2 6 4 }

{ 1 9 3 7 8 2 6 4 }

{ 1 3 7 9 8 2 6 4 }

{ 1 3 7 9 2 8 6 4 }

{ 1 3 7 9 2 4 6 8 }

{ 1 2 3 4 6 7 8 9 }

Wobei man sich beim dividen nicht wirklich an den Algo halten muss, da erst beim Mergen die Reihenfolge verändert wird, oder?

Mein Merge-Sort ist so definiert:

Merge-Sort (A,p,r)

if(p < r)
   q = (p+r)/2 //(abgerundet)
   Merge-Sort(A,p,q)
   Merge-Sort(A,q+1,r)
   Merge(A,p,q,r)

Das heißt, dass meine linke Hälfte immer die kleinere bei ungeraden Längen ist und das umgekehrt zum Algo im Link ist, oder?

Danke für den Link, gleich abgespeichert.

LG