Flettesortering

Flettesortering gør ét svært problem til mange lette: to sorterede lister er nemme at samle til én. Del listen i to, indtil hvert stykke er en enkelt værdi, og flet så stykkerne sammen igen. Det er den klassiske del og hersk-algoritme, og tiden er n log n uanset input.

To sorterede halvdele af en liste flyttet over i en bufferrække, og den mindste forreste værdi på vej op i listen igen
To sorterede halvdele af en liste flyttet over i en bufferrække, og den mindste forreste værdi på vej op i listen igen

Idéen

Fletningen er den lette del. Har man to lister, der hver er sorteret, sammenligner man deres første værdier og tager den mindste. Så sammenligner man de nye første værdier og tager igen den mindste. Når den ene liste er tom, sætter man resten af den anden bagerst. Hvert trin tager én værdi, så det kræver højst m − 1 sammenligninger at flette to lister med samlet længde m. Det bruger flettesortering til at sortere: del listen i to, sortér hver halvdel med flettesortering, og flet de to halvdele.

Et eksempel

Tag 5, 1, 4, 2, 8. Del den i 5, 1 og 4, 2, 8. Den første halvdel deles i 5 og 1, som flettes til 1, 5. Den anden halvdel deles i 4 og 2, 8; 2, 8 flettes af 2 og 8 og flettes derefter med 4 til 2, 4, 8. Til sidst flettes 1, 5 og 2, 4, 8: 1, så 2, så 4, så 5, og 8 er tilbage. Det giver 8 sammenligninger, 12 skrivninger og 4 fletninger.

Hvorfor n log n

Hver deling halverer stykkerne, så efter omkring log₂ n niveauer er hvert stykke en enkelt værdi. På vej op igen behandler hvert niveau af fletninger hver værdi én gang, hvilket er n skrivninger og færre end n sammenligninger pr. niveau. I alt er det omkring n log₂ n. For 40 værdier laver sorteringen 216 skrivninger og højst 177 sammenligninger; boblesortering kan skulle bruge 780 sammenligninger på den samme liste. Inputtets rækkefølge betyder meget mindre end for de algoritmer: for 40 værdier tager en sorteret liste 100 sammenligninger, en omvendt 116 og en tilfældig omkring 160.

Bufferen og stabilitet

For at flette to halvdele, der står ved siden af hinanden i listen, kopierer den almindelige metode dem over i en buffer og skriver dem tilbage i rækkefølge. Appen viser bufferen som den anden række søjler. Den kræver lige så meget ekstra hukommelse som listen, og det er flettesorteringens største omkostning. Til gengæld er sorteringen stabil: når de to forreste værdier er lige store, kommer den fra venstre halvdel først, så ens værdier beholder deres rækkefølge. Stabilitet er vigtig, når man sorterer poster efter ét felt efter et andet.

Historie og brug

John von Neumann beskrev flettesortering i 1945, hvilket gør den til en af de første algoritmer skrevet til en computer med lagret program. Fordi den læser og skriver data i lange forløb, var den standardmetoden til at sortere data på bånd, og den bruges stadig til filer, der er for store til hukommelsen. Timsort, som Python bruger, og som Java bruger til objekter, er en flettesortering, der først finder forløb, som allerede er sorteret, og bruger indsættelsessortering til korte stykker.

John von Neumann på sit adgangskortfoto fra Los Alamos. I 1945 beskrev han flettesortering, en af de første algoritmer skrevet til en computer med lagret program.
John von Neumann på sit adgangskortfoto fra Los Alamos. I 1945 beskrev han flettesortering, en af de første algoritmer skrevet til en computer med lagret program.

Udforsk den

Åbn appen, og tryk på Trin. Den skraverede del af listen er ved at blive delt eller flettet, og den stiplede linje markerer midten. Når en fletning starter, falder begge halvdele ned i bufferrækken; de to forreste værdier sammenlignes, og den mindste går op igen. Hold øje med tællerne: skrivningerne er de samme for alle lister med samme længde, og sammenligningerne er færrest for en sorteret eller omvendt liste og flest for en tilfældig, men aldrig flere end omkring n log₂ n.

Ofte stillede spørgsmål

Hvad er tidskompleksiteten for flettesortering?

O(n log n) i bedste, gennemsnitlige og værste tilfælde. Den almindelige version kræver O(n) ekstra hukommelse til bufferen.

Hvad er forskellen på flettesortering og quicksort?

Begge deler listen og sorterer delene. Flettesortering deler på midten uden at se på værdierne og gør sit arbejde under fletningen; quicksort gør sit arbejde under delingen ved at flytte værdier omkring et pivotelement og behøver ingen fletning. Quicksort sorterer på stedet og er ofte hurtigere i praksis, men kan blive så langsom som n² på dårligt input og er ikke stabil. Flettesortering er altid n log n og stabil.

Hvad er bottom-up-flettesortering?

En version uden rekursion: flet først enkelte naboværdier sammen til par, så par til firere og så videre, så længden fordobles hver runde. Den laver det samme arbejde som top-down-versionen, der vises her.

Er flettesortering stabil?

Ja, så længe værdien fra venstre halvdel tages først ved lighed, som denne app gør.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Prøv flettesortering