merge sort Programm

[Der_Unwissende]

Hi,
der Mergesort ist eigentlich gar nicht so schwer (merkt man leider erst wenn er fertig ist). Wichtig ist, dass du dir gut klar machst, wie er eigentlich funktioniert.
Kann dir auch nur raten zu versuchen ihn selbst zu programmieren!

Die wichtigste Grundidee ist es, dass du zwei verschiedene Schritte hast. Der erste Schritt besteht darin, dass du ein Feld in seiner Mitte teilst. Der Zweite liegt nun darin, die beiden hälften wieder sortiert zusammen zu fügen.
Das ganze rekursiv ist es auch schon.

Am leichtesten ist er zu verstehen, wenn du den mal auf einem Blatt Papier mit einem kleinen Array < 10 Elemente durchspinnst.
Nennen wir deine ganze Liste einfach A. Du zerlegst A in B und C. Sagen wir A hat 4 Elemente, dann hat B zwei und C 2. Nun machst du dass gleiche mit B und C. Als Rekursionsanker schaust du ob es mind. Zwei Elemente gibt. Also : Hat A mindestens 2 Elemente? Ja, zerlegst du in B und C (je zwei Elemente). Nun zerlegst du B (hat mindestens zwei Elemente) in B1 und B2 und C (auch zwei Elemente) in C1 und C2.
Nun machst das gleiche mit B1, B2, C1, C2. Aber jede dieser Mengen hat weniger als zwei Elemente. Ok, dann bist du mit dem zerlegen fertig (Teilproblem des Mergesorts). Nun musst du die zusammenfügen. Dazu schaust du dir B1 und B2 paarweise an. Du nimmst jetzt eine neue Liste, die so groß ist wie B1 + B2 (von der Länge, also hier 2). Dann guckst du ob B1 > B2, wenn ja, dann schreibst du B1 in die Liste, sonst B2. Dass machst du für alle Elemente von B1 und B2. Die sind dann sortiert in der Liste.
Da B1 und B2 aus B entstanden sind, ist die neue Liste also gleich dem sortierten B.
Analog für C1 und C2 sowie C.
Nennen wir die beiden Sortierten Listen B' (die aus B1 und B2 enstandene) und C' (die aus C1 und C2 enstandene). Nun weißt du, dass sie alle Elemente aus A enthalten (denn A wurde in B und C zerlegt). Also mischt du die wie gehabt. Neue Liste, für alle b aus B' einzeln gucken, ob größer als c aus C' und sortiert in die neue Liste schreiben, fertig.

Das wichtige ist hier der Divide-and-Conquer Ansatz (Teile und Herrsche). Du zerlegst dein Sortieren in sehr kleine Probleme und zwei Schritte. Du sagst, füge die sortierten Teillisten sortiert zusammen. Das ist alles.

Gruß Der Unwissende