Mergesort
Mergesort gör ett svårt problem till många enkla: två sorterade listor är lätta att slå ihop till en. Dela listan på mitten tills varje bit är ett enda värde, och sammanfoga sedan bitarna igen. Det är den klassiska söndra och härska-algoritmen, och tiden är n log n oavsett indata.
Idén
Sammanfogningen är den enkla delen. Har man två listor som var för sig är sorterade jämför man deras första värden och tar det minsta. Sedan jämför man de nya första värdena och tar det minsta igen. När den ena listan tar slut lägger man resten av den andra sist. Varje steg tar ett värde, så att sammanfoga två listor med total längd m kräver högst m − 1 jämförelser. Det använder mergesort för att sortera: dela listan på mitten, sortera varje halva med mergesort och sammanfoga de två halvorna.
Ett exempel
Ta 5, 1, 4, 2, 8. Dela den i 5, 1 och 4, 2, 8. Första halvan delas i 5 och 1, som sammanfogas till 1, 5. Andra halvan delas i 4 och 2, 8; 2, 8 sammanfogas av 2 och 8 och sedan med 4 till 2, 4, 8. Till sist sammanfogas 1, 5 och 2, 4, 8: 1, sedan 2, sedan 4, sedan 5, och 8 blir kvar. Det blir 8 jämförelser, 12 skrivningar och 4 sammanfogningar.
Varför n log n
Varje delning halverar bitarna, så efter ungefär log₂ n nivåer är varje bit ett enda värde. På vägen upp igen hanterar varje nivå av sammanfogningar varje värde en gång, vilket blir n skrivningar och färre än n jämförelser per nivå. Totalt blir det ungefär n log₂ n. För 40 värden gör sorteringen 216 skrivningar och högst 177 jämförelser; bubbelsortering kan behöva 780 jämförelser för samma lista. Indatans ordning spelar mycket mindre roll än för de algoritmerna: för 40 värden tar en sorterad lista 100 jämförelser, en omvänd 116 och en slumpad ungefär 160.
Bufferten och stabilitet
För att sammanfoga två halvor som ligger bredvid varandra i listan kopierar den vanliga metoden ut dem till en buffert och skriver tillbaka dem i ordning. Appen visar bufferten som den andra raden staplar. Den kräver lika mycket extra minne som listan, och det är mergesorts största kostnad. I gengäld är sorteringen stabil: när de två främsta värdena är lika går det från vänstra halvan först, så lika värden behåller sin ordning. Stabilitet spelar roll när man sorterar poster på ett fält i taget.
Historia och användning
John von Neumann beskrev mergesort 1945, vilket gör den till en av de första algoritmerna skrivna för en dator med lagrat program. Eftersom den läser och skriver data i långa sjok var den standardmetoden för att sortera data på band, och den används fortfarande för filer som är för stora för minnet. Timsort, som används av Python och av Java för objekt, är en mergesort som först hittar sjok som redan är sorterade och använder insättningssortering för korta bitar.
Utforska den
Öppna appen och tryck på Steg. Den skuggade delen av listan delas eller sammanfogas, och den streckade linjen markerar mitten. När en sammanfogning börjar sjunker båda halvorna ner i buffertraden; de två främsta värdena jämförs, och det minsta går upp igen. Håll koll på räknarna: skrivningarna är lika många för alla listor av samma längd, och jämförelserna är färst för en sorterad eller omvänd lista och flest för en slumpad, men aldrig fler än ungefär n log₂ n.
Ofta ställda frågor
Vad är tidskomplexiteten för mergesort?
O(n log n) i bästa, genomsnittliga och värsta fall. Den vanliga versionen behöver O(n) extra minne för bufferten.
Vad är skillnaden mellan mergesort och quicksort?
Båda delar listan och sorterar delarna. Mergesort delar på mitten utan att titta på värdena och gör sitt arbete vid sammanfogningen; quicksort gör sitt arbete vid delningen, genom att flytta värden runt ett pivotelement, och behöver ingen sammanfogning. Quicksort sorterar på plats och är ofta snabbare i praktiken, men kan bli så långsam som n² på dålig indata och är inte stabil. Mergesort är alltid n log n och stabil.
Vad är bottom-up-mergesort?
En version utan rekursion: sammanfoga först intilliggande enskilda värden till par, sedan par till fyror och så vidare, så att längden fördubblas varje runda. Den gör samma arbete som top-down-versionen som visas här.
Är mergesort stabil?
Ja, så länge värdet från vänstra halvan tas först vid lika värden, som den här appen gör.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova mergesort