b'\n_START_ARTICLE_\nMergesort\n_START_PARAGRAPH_\nMergesort is een recursief sorteer-algoritme, volgens het verdeel en heers-principe._NEWLINE_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 \xc3\xa9\xc3\xa9n element over zijn._NEWLINE_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._NEWLINE_Dit samenvoegen van gesorteerde rijen wordt op een steeds hoger niveau herhaald totdat er nog \xc3\xa9\xc3\xa9n (uiteraard gesorteerde) rij over is.\n_START_SECTION_\nProlog-voorbeeld\n_START_PARAGRAPH_\nHier is een beschrijving van mergesort in Prolog - een logische_NEWLINE_programmeertaal. Prolog heeft geen arrays en verzamelingen zowel als_NEWLINE_arrays worden dikwijls voorgesteld door "lijsten": een lege lijst is_NEWLINE_[] en een lijst waarvan het eerste element X is en wat achter X komt_NEWLINE_is T, wordt voorgesteld als [X|T]_NEWLINE_wat achter\xc2\xa0% staat is commentaar_NEWLINE_mergesort is als een procedure met twee argumenten: het eerste is_NEWLINE_input (de lijst die we willen sorteren) en de tweede is output,_NEWLINE_namelijk het resultaat van de sorteeroperatie_NEWLINE_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 */_NEWLINE_split(Lijst,H1,H2),/* split de lijst in 2 helften */_NEWLINE_mergeSort(H1,S1),/* mergesort deze helften */_NEWLINE_mergeSort(H2,S2),/* mergesort deze helften */_NEWLINE_merge(S1,S2,SortedList).        /* merge de 2 gesorteerde helften */_NEWLINE__NEWLINE_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 */_NEWLINE_split(T,H1,H2)./* en ga verder met de rest van de lijst */_NEWLINE__NEWLINE_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*/_NEWLINE_Head1<Head2,/* predicate*/_NEWLINE_!,_NEWLINE_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 */_NEWLINE_merge([H1|T1],T2,S)./* en ga verder met tail2 en de hele eerste lijst */\n_START_SECTION_\nJava-voorbeeld\n_START_PARAGRAPH_\nHet 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):_NEWLINE_  void mergesort(Comparable[] ao){_NEWLINE_    if (ao.length <= 1){_NEWLINE_      return; // klaar_NEWLINE_    }_NEWLINE_    /* splitsen */_NEWLINE_    int i1= ao.length / 2;_NEWLINE_    Comparable[] aoL= new Comparable[i1];_NEWLINE_    for (int i= 0; i < i1; i++){_NEWLINE_      aoL[i]= ao[i];_NEWLINE_    }_NEWLINE_    Comparable[] aoR= new Comparable[ao.length - i1];_NEWLINE_    for (int i= i1; i < ao.length; i++){_NEWLINE_      aoR[i - i1]= ao[i];_NEWLINE_    }_NEWLINE_    /* subreeksen sorteren */_NEWLINE_    mergesort(aoL);_NEWLINE_    mergesort(aoR);_NEWLINE_    /* subreeksen samenvoegen (ritsen) */_NEWLINE_    /* ao kunnen we hergebruiken */_NEWLINE_    int iL= 0;_NEWLINE_    int iR= 0;_NEWLINE_    for (int i= 0; i < ao.length; i++){_NEWLINE_      if (iL >= aoL.length){_NEWLINE_        ao[i]= aoR[iR++];_NEWLINE_      } else if (iR >= aoR.length){_NEWLINE_        ao[i]= aoL[iL++];_NEWLINE_      } else if (aoL[iL].compareTo(aoR[iR]) <= 0){_NEWLINE_        ao[i]= aoL[iL++];_NEWLINE_      } else{_NEWLINE_        ao[i]= aoR[iR++];_NEWLINE_      }_NEWLINE_    }_NEWLINE_  }\n_START_SECTION_\nC-voorbeeld\n_START_PARAGRAPH_\nDe volgende C functie sorteert de array "data" met "lengte" aantal elementen volgens het mergesort-algoritme:_NEWLINE_void mergesort(int data[],int lengte){_NEWLINE_  int i1=0, i2=0;         // huidige plaats in groepen_NEWLINE_  int *groep1, *groep2;   // begin van groepen_NEWLINE_  int lengte1, lengte2;   // lengtes van groepen_NEWLINE_  int gesorteerd[lengte]; // gesorteerde data_NEWLINE_  int tijdelijk;_NEWLINE__NEWLINE_  if (lengte > 1){_NEWLINE_    // indien lengte 1 of kleiner is valt er niets te sorteren_NEWLINE_    // verdeel in groepen_NEWLINE_    groep1= data;_NEWLINE_    groep2= data + lengte / 2;_NEWLINE_    // zoek lengte van elke groep_NEWLINE_    lengte1= lengte / 2;_NEWLINE_    lengte2= lengte - lengte1;_NEWLINE_    // mergesort_NEWLINE_    mergesort(groep1, lengte1);_NEWLINE_    mergesort(groep2, lengte2);_NEWLINE__NEWLINE_    // merge_NEWLINE_    for (tijdelijk= 0; tijdelijk < lengte; tijdelijk++){_NEWLINE_      if (i1==lengte1){_NEWLINE_        // einde groep1, neem huidig van 2_NEWLINE_        gesorteerd[tijdelijk]= groep2[i2];_NEWLINE_        i2++;_NEWLINE_      } else if (i2==lengte2){_NEWLINE_        // einde groep2,neem huidig van 1_NEWLINE_        gesorteerd[tijdelijk]= groep1[i1];_NEWLINE_        i1++;_NEWLINE_      } else if (groep1[i1] < groep2[i2]){_NEWLINE_        // huidig van 1 is kleiner,neem dit_NEWLINE_        gesorteerd[tijdelijk]= groep1[i1];_NEWLINE_        i1++;_NEWLINE_      } else{_NEWLINE_        // huidig van 2 is kleiner,neem dit_NEWLINE_        gesorteerd[tijdelijk]= groep2[i2];_NEWLINE_        i2++;_NEWLINE_      }_NEWLINE_    }_NEWLINE_    // kopieer gesorteerd naar data_NEWLINE_    memcpy(data, gesorteerd, lengte* sizeof(int));_NEWLINE_  }}\n_START_SECTION_\nPython code\n_START_PARAGRAPH_\ndef mergesort(rij):_NEWLINE_    if len(rij) <= 1:_NEWLINE_        return rij                      #stopconditie_NEWLINE_    midd = int(len(rij)/2)_NEWLINE_    links = mergesort(rij[:midd])       #recursieve oproep op linkerdeel_NEWLINE_    rechts = mergesort(rij[midd:])      #recursieve oproep op rechterdeel_NEWLINE_    teller = 0_NEWLINE_    while len(links)!=0 and len(rechts)!=0:_NEWLINE_        if links[0] < rechts[0]:         #vergelijk de eerste van links met de eerste van rechts_NEWLINE_            rij[teller] = links.pop(0)   #verwijder eerste van links en plak ze in de rij_NEWLINE_        else:_NEWLINE_            rij[teller] = rechts.pop(0)  #verwijder eerste van rechts en plak ze in de rij_NEWLINE_        teller += 1_NEWLINE_    return rij[:-len(links+rechts)] + links + rechts  #of links of rechts is leeg, dus dit kan'