Algorithmen und Datenstrukturen in C/ Mergesort

Mergesort ist ein Divide-and-Conquer-Sortierverfahren. Eine Liste der Länge n wird solange rekursiv geteilt, bis n einelementige Teillisten entstehen. Nun folgt der eigentliche Sortiervorgang: Man nimmt immer zwei Teillisten und fügt diese zu einer neuen sortierten Teilliste zusammen, indem man immer das kleinste Element der beiden Listen streicht und in die neue Teilliste einfügt. Dieses Verfahren muss dann solange wiederholt werden, bis es nur noch eine Teilliste gibt. Die folgende Abbildung zeigt an einem Beispiel, wie der Algorithmus arbeitet:

Die Komplexität des Algorithmus ist O(n*log(n)).

Implementierung in C

In C kann Mergesort z. B. folgendermaßen implementiert werden:

 void MergeSort(int liste[], int groesse){
 
     if(groesse > 1){
  
         int haelfte1[groesse/2];
         int haelfte2[(groesse + 1)/2];
         int i;
         for(i = 0; i < groesse/2; ++i)
             haelfte1[i] = liste[i];
         for(i = groesse/2; i < groesse; ++i)
             haelfte2[i - groesse/2] = liste[i];
  
         MergeSort(haelfte1,groesse/2);
         MergeSort(haelfte2,(groesse + 1)/2);
  
         int *pos1 = &haelfte1[0];
         int *pos2 = &haelfte2[0];
         for(i = 0; i < groesse; ++i){
             if(*pos1 <= *pos2){
                 liste[i] = *pos1;
                 if (pos1 != &haelfte2[(groesse+1)/2 - 1]) { // pos1 nicht verändern, wenn der größte Wert mehrmals vorkommt
                     if(pos1 == &haelfte1[groesse/2 - 1]){
                         pos1 = &haelfte2[(groesse+1)/2 - 1];
                     }
                     else{
                         ++pos1;
                     }
                 }
             }
             else{
                 liste[i] = *pos2;
                 if(pos2 == &haelfte2[(groesse + 1)/2 - 1]){
                     pos2 = &haelfte1[groesse/2 - 1];
                 }
                 else{
                     ++pos2;
                 }
             }
         }
     }
 }

Mergesort wird hier als Funktion realisiert, der zwei Parameter - das zu sortierende Array und dessen Länge - übergeben werden. Die if-Abfrage in der ersten Zeile des Funktionsrumpfes führt zum Rekursionsabbruch: Falls das Array nur aus einem Element besteht, muss es nicht sortiert werden. Andernfalls werden die Werte des Arrays in zwei Teilarrays kopiert, die anschließend durch rekursive Aufrufe von Mergesort sortiert werden. Nach dem Sortieren werden die beiden Teilarrays zusammengefügt. Für beide Teilarrays wird jeweils ein Pointer angelegt, der immer auf das kleinste Element, das noch nicht in das große Array eingefügt wurde, zeigt. Da die Teilarrays sortiert sind, muss dazu lediglich nach jedem Einfügen der Zeiger auf die nächste Stelle gesetzt werden. Möglich ist das natürlich nur, solange sich noch in beiden Arrays Elemente befinden, die noch nicht in das große Array kopiert wurden. Wenn das Ende eines der beiden Teilarrays erreicht ist, dann müssen noch alle restlichen Elemente des anderen Teilarrays durchlaufen und der Reihe nach in das große Array kopiert werden. Um das zu erreichen, wird der Zeiger des abgearbeiteten Arrays auf die letzte Stelle des anderen Teilarrays gesetzt.

<< Shellsort | Inhaltsverzeichnis | Heapsort >>