Mergesort

Mergesort is een recursief sorteeralgoritme, volgens het verdeel en heers-principe. Mergesort werkt door een rij te sorteren elementen eerst in twee ongeveer even grote (ongesorteerde) 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 voorste 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.

Mergesort

Pseudocode

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.

De complexiteitsgraad van mergesort is bij het sorteren van n items in het slechtste geval O(n log n), waarvan de code die twee gesorteerde rijen samenvoegt in O(n) tijd verloopt (lineair).

Prolog-voorbeeld

Hier is een beschrijving van mergesort in Prolog - een logische programmeertaal. Prolog heeft geen arrays. 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([], []).  				/* lege lijst is lege gesorteerde lijst */
mergeSort([X], [X]). 			        /* lijst met 1 element is een gesorteerde lijst met 1 element */
mergeSort(Lijst,SortedList):-	                /* mergeSort de Lijst en vang het resultaat op in de Sortedlijst */
	split(Lijst,H1,H2),			/* split de lijst in 2 helften */
	mergeSort(H1,S1),			/* mergesort deze helften */
	mergeSort(H2,S2),			/* mergesort deze helften */
	merge(S1,S2,SortedList).	        /* merge de 2 gesorteerde helften */
	
split([], [], []).				/* split van een lege lijst geeft 2 lege helften */
split([X], [X], []).				/* split met 1 element geeft 1 helft met dat element erin en een lege lijst (bij een oneven lijst)*/
split([X,Y|T], [X|H1], [Y|H2]):-			/* voeg respectievelijk X en Y aan de eerste en tweede helft toe */
	split(T,H1,H2).				/* en ga verder met de rest van de lijst */
	
merge([], [], []).				/* merge van 2 lege lijsten is een lege lijst */
merge(X,[],X).					/* merge van een lege lijst met een niet-lege lijst is die niet-lege lijst */
merge([],Y,Y).					/* merge van een lege lijst met een niet-lege lijst is die niet-lege lijst */
merge([Head1|Tail1], [Head2|Tail2], [Head1|S]):-  /* als  head1 kleiner is dan head2 voeg head1 dan toe aan de gemergde lijst*/
	Head1<Head2,				/* predicate*/
	!,
	merge(Tail1,[Head2|Tail2],S).		/* en ga verder met tail1 en de hele tweede lijst*/
merge([H1|T1], [H2|T2], [H2|S]):- 		/* als head1 groter is als head2 voeg dan head2 toe aan de gemergde lijst */
	merge([H1|T1],T2,S).			/* en ga verder met tail2 en de hele eerste lijst */

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(Comparable[] ao){
    if (ao.length <= 1){
      return; // klaar
    }
    /* splitsen */
    int i1= ao.length / 2;
    Comparable[] aoL= new Comparable[i1];
    for (int i= 0; i < i1; i++){
      aoL[i]= ao[i];
    }
    Comparable[] aoR= new Comparable[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 (aoL[iL].compareTo(aoR[iR]) <= 0){
        ao[i]= aoL[iL++];
      } else{
        ao[i]= aoR[iR++];
      }
    }
  }

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
    memcpy(data, gesorteerd, lengte* sizeof(int));
  }
}

Python-voorbeeld

Python-code

 def mergesort(rij):
    if len(rij) <= 1:
        return rij                      #stopconditie
    midd = int(len(rij)/2)
    links = mergesort(rij[:midd])       #recursieve oproep op linkerdeel
    rechts = mergesort(rij[midd:])      #recursieve oproep op rechterdeel
    teller = 0
    while len(links)!=0 and len(rechts)!=0:
        if links[0] < rechts[0]:         #vergelijk de eerste van links met de eerste van rechts
            rij[teller] = links.pop(0)   #verwijder eerste van links en plak ze in de rij
        else:
            rij[teller] = rechts.pop(0)  #verwijder eerste van rechts en plak ze in de rij
        teller += 1
    return rij[:-len(links+rechts)] + links + rechts  #of links of rechts is leeg, dus dit kan