Mergesort

Van Wikipedia

Mergesort is een recursief sorteer-algoritme. Mergesort werkt door een rij te sorteren elementen eerst in twee ongeveer even grote (ogesorteerde) rijen te verdelen en dat te herhalen totdat er alleen nog rijen met één element over zijn. Dan worden de rijen weer twee aan twee samengevoegd, geritst als het ware, waarbij steeds de voorsten van de twee gesorteerde rijen met elkaar worden vergeleken om te bepalen welke het volgende element in de gesorteerde rij moet worden. Dit samenvoegen van gesorteerde rijen wordt op een steeds hoger niveau herhaald totdat er nog één (uiteraard gesorteerde) rij over is.

Hier volgt een pseudocode-voorbeeld vertrekkend van de rij {2,1,2^*,3}:

verdeel {2,1,2',3} in twee delen: {2,1} en {2',3}

verdeel {2,1} in twee delen: {2} en {1}

voeg {2} en {1} op volgorde samen tot {1,2}

verdeel {2',3} in twee delen: {2'} en {3}

voeg {2'} en {3} op volgorde samen tot {2',3}

voeg {1,2} en {2',3} op volgorde samen tot {1,2,2',3}

Als bij het samenvoegen in dezelfde volgorde wordt gewerkt als bij het verdelen, is het algoritme stabiel: de volgorde van 2 en 2' in het voorbeeld blijft bij het sorteren onveranderd.

[bewerk] Prolog-voorbeeld

Hier is een beschrijving van mergesort in Prolog - een logische programmeertaal. Prolog heeft geen arrays en verzamelingen zowel als arrays worden dikwijls voorgesteld door "lijsten": een lege lijst is [] en een lijst waarvan het eerste element X is en wat achter X komt is T, wordt voorgesteld als [X|T] wat achter % staat is commentaar mergesort is als een procedure met twee argumenten: het eerste is input (de lijst die we willen sorteren) en de tweede is output, namelijk het resultaat van de sorteeroperatie

mergesort(Lijst, SortedLijst) :- % SortedLijst is Lijst gesorteerd indien

       (Lijst = [] ->
               SortedLijst = []     % indien Lijst leeg is dan is zijn gesorteerde versie ook leeg
       ;
               split(Lijst, Lijst1, Lijst2),  % anders: splits Lijst in twee delen
               mergesort(Lijst1, SortedLijst1),
               mergesort(Lijst2, SortedLijst2),
               merge(SortedLijst1, SortedLijst2, SortedLijst)
       ).

merge(L1, L2, Result) :-

       (
         L1 = [] ->
               Result = L2   % mergen van een lege lijst en L2 geeft als resultaat L2
       ;
         L2 = [] ->
               Result = L1   % idem voor L1
       ;
         L1 = [X1|R1],       % L1 is niet leeg, dus heeft een eerst element en een rest
         L2 = [X2|R2],       % idem voor L2
         (X1 < X2 ->
               Result = [X1|RestResult],          % X1 is kleiner dan X2 en moet dus van voor in het
               merge(R1, [X2|R2], RestResult)     % resultaat; vervolgens berekenen we de rest ervan
         ;
               Result = [X2|RestResult],          % X1 is niet kleiner dan X2; dus moet X2 van voor
               merge([X1|R1], R2, RestResult)     % in het resultaat
         )
       ).

split([], [], []). % een lege lijst kan men enkel splitsen in twee lege lijsten split([X], [X], []). % een lijst met slechts 1 element, kan men splitsen in die lijst en een lege lijst split([A,B|Rest], [A|R1], [B|R2]) :- % een lijst die begint met A en B, splitst men door

       split(Rest, R1, R2).          % A in de ene output lijst te steken, B in de andere en dan
                                     % bereken je de rest van de output lijsten vertrekkend van de
                                     % invoer zonder A en B

[bewerk] Java-voorbeeld

Het onderstaand Java-codefragment sorteert de array ao (dat kan een String-array zijn, maar ook een array van een ander type zolang het maar Comparable is):

 void mergesort(Object[] ao){
   if (ao.length <= 1){
     return; // klaar
   }
   /* splitsen */
   int i1= ao.length / 2;
   Object[] aoL= new Object[i1];
   for (int i= 0; i < i1; i++){
     aoL[i]= ao[i];
   }
   Object[] aoR= new Object[ao.length - i1];
   for (int i= i1; i < ao.length; i++){
     aoR[i - i1]= ao[i];
   }
   /* subreeksen sorteren */
   mergesort(aoL);
   mergesort(aoR);
   /* subreeksen samenvoegen (ritsen) */
   /* ao kunnen we hergebruiken */
   int iL= 0;
   int iR= 0;
   for (int i= 0; i < ao.length; i++){
     if (iL >= aoL.length){
       ao[i]= aoR[iR++];
     } else if (iR >= aoR.length){
       ao[i]= aoL[iL++];
     } else if (((Comparable) aoL[iL]).compareTo((Comparable) aoR[iR]) <= 0){
       ao[i]= aoL[iL++];
     } else{
       ao[i]= aoR[iR++];
     }
   }
 }

[bewerk] C-voorbeeld

De volgende C functie sorteert de array "data" met "lengte" aantal elementen volgens het mergesort-algoritme:

 void mergesort(int data[],int lengte){
   int i1=0,i2=0; //huidige plaats in groepen
   int *groep1,*groep2; //begin van groepen
   int lengte1,lengte2; //lengtes van groepen
   int gesorteerd[lengte];  //gesorteerde data
   int tijdelijk;

   if(lengte>1){ //indien lengte 1 of kleiner is valt er niets te sorteren
     //verdeel in groepen
     groep1=data;groep2=data+lengte/2;
     //zoek lengte van elke groep
     lengte1=lengte/2;
     lengte2=lengte-lengte1;
     //mergesort
     mergesort(groep1,lengte1);
     mergesort(groep2,lengte2);
     //merge
     for(tijdelijk=0;tijdelijk<lengte;tijdelijk++){
       if(i1==Lengte1){  //einde groep1,neem huidig van 2
         gesorteerd[tijdelijk]=groep2[i2];
         i2++;
       }else if(i2==Lengte2){ //einde groep2,neem huidig van 1
         gesorteerd[tijdelijk]=groep1[i1];
         i1++;
       }else if(groep1[i1]<groep2[i2]){
         //huidig van 1 is kleiner,neem dit
         gesorteerd[tijdelijk]=groep1[i1];
         i1++;
       }else{
         //huidig van 2 is kleiner,neem dit
         gesorteerd[tijdelijk]=groep2[i2];
         i2++;
       }
     }
     //kopieer gesorteerd naar data
     for(tijdelijk=0;tijdelijk<lengte;tijdelijk++) data[tijdelijk]=gesorteerd[tijdelijk];
   }
 }