Mit dem Merge Sort - Sortierverfahren werden 2 bereits Sortiert Teilfolgen miteinander vermischt. Dieses Verfahren läßt sich ähnlich wie Quicksort nach dem "Teile und Herrsche" - Prinzip anwenden. Teile die Daten in 2 Teilen, sortiere jeden der beiden Teile. Danach werden diese beiden Teile zu einer insgesamten Folge wieder vermischt.

Dazu verwendet man auch den selben Ansatz wie bei Quicksort. Man teilt die Daten in zwei Teilen, anschließend wird die linke Seite der beiden Daten rekuriv sortiert und als nächstes die rechte Seite rekursiv.

Danach kommt der Programmtechnisch etwas kompliziertere Teil, das Mischen der beiden Teile. Dabei muss darauf geachtet werden, dass beide Teile abwechselnd kopieren (mischen). Oder sollte eine Hälfte schneller fertig sein als die andere, sollte die andere Ihre Arbeit auch noch beenden.

Dies wird dadurch ereicht in dem die rechte Seite von rechts nach links durchläuft und die linke Seite von links nach rechts. Sobald die beiden Seiten aufeinandertreffen ist das Sortieren beendet.

Hier nun der Algorithmus zu Merge Sort.....

/*Download:merge.c*/ #include <stdio.h> void merge(int [], int, int); void mergesort(int array[], int low, int high) { int m; if(low<high) { m=(low+high)/2; mergesort(array, low, m); mergesort(array, m+1, high); merge(array, low, high); } } void merge(int array[], int low, int high) { int i,j,k=0,m, n=high-low+1; int b[high-low+1]; m=(low+high)/2; /*linke Hälte in Array b kopieren*/ for(i=low; i<=m; i++) b[k++] = array[i]; /*rechte Hälfte in umgekehrter Reihenfolge in Array b kopieren*/ for(j=high; j>=m+1; j--) b[k++] = array[j]; i=0; j=n-1; k=low; /*Nun das Nächstgrößere Element zurückkopieren bis i und j sich überkreuzen*/ while(i<=j) (b[i]<=b[j])?(array[k++]=b[i++]):(array[k++]=b[j--]); } int main() { int i; int test_array[] = { 4, 5, 3, 8, 1, 8, 2 }; mergesort(test_array, 0, 6); for(i=0; i<=6; i++) printf("%d ",test_array[i]); printf("\n"); return 0; }