- Del som sammanfogas
- Jämförda
- Tillbakaskrivna
- Sammanfogade hittills
Mergesort
Mergesort är en söndra och härska-algoritm. Den delar listan på mitten, sorterar varje halva på samma sätt och sammanfogar de två sorterade halvorna genom att hela tiden ta det minsta främsta värdet. Se halvorna flyttas till en buffertrad och skrivas tillbaka i ordning, i valfri hastighet eller ett steg i taget, och räkna jämförelser, skrivningar och sammanfogningar. Tryck på Spela för att se sorteringen, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa vart som helst. Rutorna räknar jämförelser, skrivningar tillbaka till listan och sammanfogningar. Välj hur många staplar, hur de börjar, eller skriv dina egna tal. När tavlan är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Välj antal staplar och startordning: slumpad, nästan sorterad, omvänd eller med få unika värden. Eller skriv dina egna tal.
- Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst i sorteringen.
- Följ varje sammanfogning: de två sorterade halvorna går ner i bufferten, och det minsta främsta värdet går upp igen, ett i taget.
Så fungerar mergesort
Ett enda värde är redan sorterat. Är listan längre delar man den i två halvor och sorterar varje halva med mergesort. Sedan sammanfogar man dem: titta på det främsta värdet i varje halva, flytta det minsta till resultatet och upprepa tills båda halvorna är tomma. Eftersom båda halvorna är sorterade blir resultatet också sorterat.
Alltid n log n
Att dela på mitten om och om igen ger ungefär log₂ n nivåer, och varje nivå av sammanfogningar skriver varje värde en gång, så sorteringen gör ungefär n log₂ n skrivningar och högst lika många jämförelser. Till skillnad från bubbelsortering, urvalssortering och insättningssortering växer det inte med n², och listans ordning spelar mycket mindre roll. Priset är en buffert lika lång som listan. Mergesort är också stabil, och därför är den grunden för sorteringen i Python och Java.
Ofta ställda frågor
Hur fungerar mergesort?
Den delar listan på mitten, sorterar varje halva med mergesort och sammanfogar de två sorterade halvorna genom att hela tiden ta det minsta av deras främsta värden. En lista med ett värde är redan sorterad, så där slutar delningen.
Hur många jämförelser gör mergesort?
Högst ungefär n log₂ n − n + 1 och minst ungefär hälften av n log₂ n, för n värden. För 40 värden är det högst 177. Skrivningarna tillbaka till listan är alltid lika många för ett givet n: en per värde på varje nivå av sammanfogning.
Varför behöver mergesort extra minne?
Att sammanfoga två halvor på plats är svårt att göra snabbt, så vanlig mergesort kopierar halvorna till en buffert och skriver tillbaka dem i ordning. Bufferten är lika lång som listan, och det är den största nackdelen jämfört med quicksort och heapsort.
Är mergesort stabil?
Ja. 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 ursprungliga ordning.
Skickas mina tal någonstans?
Nej. Sorteringen körs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor