Flettesortering

Visuel gennemgang af flettesortering. Det ses hvordan listen bliver delt op i mindre "sub-lister" indtil de består af kun ét element, hvorefter de bliver flettet sammen til den sorterede liste.

Flettesortering (engelsk: Merge sort) er en sammenligningsbaseret sorteringsalgoritme der bygger på princippet om "Divide and conquer" inden for datalogien. Algoritmen udnytter flette-funktionen (deraf navnet) af mindre sorterede lister til effektivt at flette større og større dele af den oprindelige liste sammen til én stor sorteret liste.

Algoritmen blev opfundet af John von Neumann i 1945.

Beskrivelse

Flettesorterinng forgår af to dele:

1. Opdel input listen på midten og sorter de to lister individuelt. I tilvældet hvor listen kun er ét element er den sorteret.
2. Flet de to sorterede lister sammen med flette-funktionen

Det bemærkes at første step er rekursivt, altså kalder algoritmen sig selv, denne gang på en mindre liste. Dette betyder at algoritmen "dykker" ned i forgreninger indtil den når det enkelte element. Idet den når bunden er listen trivielt sorteret, da den blot består af et element og anden del algoritmen kan da træde i kraft hvor de to små lister flettes sammen. På denne måde når algoritmen systematisk igennem hele listen hvor den til sidst fletter de to sidste, nu sorterede lister, sammen til den endelige sorterede liste.

Implementation

Teoretisk pseudokode implementering

Flette-funktionen sammensætter to sorterede lister således at den endelige liste stadig er sorteret. Der udnyttes at listerne allerede er sorterede og det giver anledning til en såkaldt invariant. Dette kan forstås hvis listerne ses som sorteret fra venstre mod højre. Hvis et element i den ene liste er større end et element i den anden liste, må et element længere til højre i den første liste nødvendigvis også være større end elementet i den anden liste. Dette er rygraden til effektiviteten af fletning.

function flet(list L, p, q, r)
   n1 = q - p + 1
   n2 = r - q
   list V = [1..n1 + 1]
   list H = [1..n2 + 1]
   for i = 1 to n1
      V[i] = L[p + i - 1]
   for j = 1 to n2
      H[j] = L[q + j]
   V[n1 + 1] = uendelig
   H[n2 + 1] = uendelig
   i = 1
   j = 1
   for k = p to r
      if V[i] <= H[j]
         L[k] = V[i]
         i = i + 1
      else 
         L[k] = H[j]
         j = j + 1

I dette tilfælde tager flette-funktionen én inputliste som er sorteret fra p til q og fra q+1 til r. Inputlisten deles op i to lister V og H gående fra henholdsvis p til q og p+1 til r. Yderligere tilføjes et ekstra element som har størrelsen uendelig for at signalere hvornår listens enepunkt er nået. Herefter løbes hele vejen fra p til r hvor der bestemmes hvorvidt elementet fra V eller H skal sættes ind. Når et element fra enten V eller H sættes ind 'flyttes' henholdsvis i eller j én plads til det næste element i den respektive liste. Resultatet er en gennemgang af de to lister hvor den mindste hele tiden bliver kopieret til den oprindelige liste, og man ender da ud med én sorteret liste.

Selve flettesorteringen anvender flette-funktionen til at sammenflette større og større lister. Dette foregår ved at opdele input-listen i to tilnærmelsesvis lige store lister og rekursivt sortere dem hver især, efterfulgt af en sammenfletning.

function flettesorter(list L, p, r)
   q = floor((p + r)/2)
   flettesorter(L, p, q)
   flettesorter(L, q + 1, r)
   flet(L, p, q, r)

Tidskompleksitet

Algoritmens kørselstid er i værste tilfælde $O(n\log(n))$ hvilket er det bedste mulige for en sammenligningsbaseret sorteringsalgoritme. Dette er dog også den bedste mulige kørselstid og dermed også den gennemsnitlige kørselstid.

Kørselstiden $O(n\log(n))$ kan nogenlunde intuitivt gennemskues hvis man ser på den binære træ-lignende struktur de to rekursive kald i algoritmen skaber, som ender ud med dybden $\log(n)$ og bredden $n$. Dette er dog ikke en formel udledning.

I praksis

Flettesortering er en yderst paralleliserbar algoritme, hvilket gør den meget anvendelig i forbindelse med computersystemer der kan anvende paralleliserede beregninger.

Et eksempel er Java som for funktionen Arrays.sort() Arkiveret 11. november 2020 hos Wayback Machine bruger en implementering af flettesortering eller Quicksortering alt efter datatypen og yderligere bruger indsættelsessortering for sortering af mindre end syv elementer.

Reference

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.