Hva er det som gjør mergesort raskere enn de enklere sorteringsalgoritmene?

Sortering er et av de grunnleggende problemene i informatikk. Det går ut på å finne en god fremgangsmåte for å ta en liste med for eksempel tall og sortere dem etter størrelse. Om man er på hyttetur og sitter med en kortstokk som har sett bedre dager, så er det vanlig å sortere den for å finne ut om det er noen kort som mangler.

Ofte kan det være godt nok bare å telle kortene, om man passer på om det er jokere.

For å skjønne hvordan man tenker på sortering innenfor informatikk, så er det om best å tenke på at man skal sortere kjempestore lister. Tusener eller millioner av tall. Da er det åpenbart at man ikke bare kan finne det største tallet ved å kaste et blikk på listen, men at man må jobbe seg gjennom hele listen element for element. Vi vil også anta at vi ikke vet noe særlig om tallene som er i listen - ulikt en kortstokk, hvor vi vet at vi har nøyaktig tretten kort av hver farge, med kjente verdier.

Den mest intuitive sorteringsalgoritmen, og den som mange bruker om de skal sortere en kortstokk, heter insertion sort. Den går ut på at man flytter ett og ett kort fra den usorterte bunken over i en ny bunke, slik at den nye bunken til enhver tid er sortert. Det første kortet kommer automatisk på rett plass - det neste må man se om skal før eller etter det forrige, også videre.

Problemet med insertion sort er at det mot slutten er veldig mye jobb å finne riktig plass for de nye kortene, fordi bunken man setter kortene inn i blir stadig større.

Speilbildet til insertion sort heter selection sort. Der tar man ikke nye kort fra toppen av den usortere bunken. Isteden leter man gjennom den usorterte bunken etter det aller minste elementet, kanskje ruter to, og legger det til i den nye listen. Så leter man frem ruter tre, ruter fire, ... Selection sort har akkurat samme problemet som insertion sort - i starten blir man sittende med å lete gjennom en stor bunke mange ganger, hele tiden for å finne ett, bestemt element.

En effektiv sorteringsalgoritme prøver å unngå begge disse ytterpunktene. Løsningen er å ikke kreve fullkommen sortering underveis. Mergesort deler opp det som skal sorteres i mindre bunker og sorterer hver av disse bunkene for seg, for til å slutt å slå dem sammen igjen. Dette høres ut som ekstraarbeid, men er svært lønnsomt om det er mange nok elementer som skal sorteres.

Det magiske med mergesort er at vi får endel sammenligninger gratis, uten å måtte bla så skrekkelig mye gjennom kortstokken, når vi til slutt slår sammen sorterte bunker. Om vi vet at alle elementene i en bunke er større enn det største elementet i en annen, så vet vi umiddelbart at alle elementene i den første bunken er større en alle elementene i den andre bunken.

Det er denne typen besparelser som gjør mergesort, quicksort og heapsort raskere enn de enkle sorteringsalgoritmene.