Flettesortering

Flettesortering, eller merge sort, er en stabil, sammenligningsbasert sorteringsalgoritme som bruker divide-and-conquer-tilnærmingen. Den deler en rekke i to halvdel, sorterer hver halvdel rekursivt og fletter de to sorterte halvdelene til en hel sortert rekke.

Algoritmen består av to faser: dele og flette. På delefasen deles listen rekursivt helt til hver del består av ett element. På flettefasen sammenlignes det neste uvalgte elementet fra venstre og fra høyre, og det minste legges til i den nye, sorterte listen. Denne prosessen gjentas til alle elementer er flettet inn i en sortert rekke.

Flettesortering har tidskompleksitet O(n log n) i alle kjøremåter (beste, verste og gjennomsnitt). Plassmessig krever klassisk implementasjon ekstra bufferplass på omtrent n elementer, noe som gir O(n) ekstra plass. Det finnes in-place-varianter og spesialtilfeller (for eksempel ved bruk av lenkelister) som kan redusere minnebruken i visse situasjoner, men de er ofte mer komplekse å implementere.

Flettesortering er stabil, det vil si at elementer med lik nøkkel beholder sin opprinnelige rekkefølge etter sortering. Den er gunstig når stabilitet er viktig eller når store datasett deles opp og flettes i faser, slik som i ekstern sortering eller streaming. Det finnes også en iterativ, bottom-up-variant som bygger sorteringen ved å flette sublister av stadig større størrelse.

Oppsummert er flettesortering en pålitelig og generell sorteringsmetode med forutsigbar yteevne og god stabilitet, men den krever vanligvis mer minne enn enkelte in-place-alternativer.