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.
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 logischeprogrammeertaal. Prolog heeft geen arrays. Verzamelingen zowel alsarrays worden dikwijls voorgesteld door "lijsten": een lege lijst is[] en een lijst waarvan het eerste element X is en wat achter X komtis T, wordt voorgesteld als [X|T]wat achter % staat is commentaarmergesort is als een procedure met twee argumenten: het eerste isinput (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