title: Mergesort
text: 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.
  
  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
  
  Sorteeralgoritme