Mergesortering
↑Snabböversikt
Section titled “Snabböversikt”Mergesortering delar upp listan i mindre delar och slår sedan ihop dem i sorterad ordning. Tidsåtgången är förutsägbar även för stora listor.
| Egenskap | Kom ihåg |
|---|---|
| Vanlig tidskomplexitet | O(n log n) |
| Extra minne | O(n) |
| Stabil? | Ja, med implementationen nedan |
| Passar bäst när | Du vill ha förutsägbar prestanda även på stora listor |
Se algoritmen arbeta
Section titled “Se algoritmen arbeta”Staplarna visar värden och positioner. Välj Nästa för att undersöka ett moment eller Spela för hela förloppet. Testa egna tal, gärna en redan sorterad och en omvänt sorterad lista.
Beskriv själv vad algoritmen gör just nu.
Varför behövs det här steget?
Försök förutse nästa steg.
Lila: jämförs eller flyttas | Grönt: färdig del | Orange: aktuellt arbetsområde
Ett exempel på delning och sammanslagning
Section titled “Ett exempel på delning och sammanslagning”
Diagrammet visar hur listan först delas till enskilda element. Därefter sammanfogas de sorterade delarna från botten och upp.
Steg för steg
Section titled “Steg för steg”- Hitta mitten. Dela intervallet i en vänster och en höger del.
- Sortera halvorna. Gör samma sak rekursivt tills varje intervall innehåller ett element.
- Använd en tillfällig buffert. Vid sammanslagningen är varje halva redan sorterad.
- Jämför de första återstående värdena. Lägg det mindre värdet i bufferten. Vid lika värden väljer vi vänster sida först för att behålla stabilitet.
- Kopiera resten. När ena halvan tar slut kan återstoden av den andra kopieras direkt.
- Kopiera tillbaka. Nu är hela intervallet sorterat och den rekursiva processen fortsätter.
Följ ett litet exempel för hand
Section titled “Följ ett litet exempel för hand”Med [7, 3, 5] delar vi i [7] och [3, 5], och sedan i [3] och [5]. Slå ihop till [3, 5]. Jämför därefter första kvarvarande värdet på varje sida: 3, 5, 7. Resultatet blir [3, 5, 7].
Implementation i C#
Section titled “Implementation i C#”static void MergeSort(int[] a){ int[] buffer = new int[a.Length]; Sort(0, a.Length);
void Sort(int start, int end) { if (end - start <= 1) return; int middle = start + (end - start) / 2; Sort(start, middle); Sort(middle, end);
int left = start, right = middle; for (int k = start; k < end; k++) { if (right == end || (left < middle && a[left] <= a[right])) buffer[k] = a[left++]; else buffer[k] = a[right++]; } Array.Copy(buffer, start, a, start, end - start); }}#include <vector>#include <algorithm>void mergeSort(std::vector<int>& values) { if (values.size() < 2) return; std::vector<int> buffer(values.size()); auto sort = [&](auto&& self, int lo, int hi) -> void { if (hi - lo < 2) return; int mid = lo + (hi - lo) / 2; self(self, lo, mid); self(self, mid, hi); std::merge(values.begin()+lo, values.begin()+mid, values.begin()+mid, values.begin()+hi, buffer.begin()+lo); std::copy(buffer.begin()+lo, buffer.begin()+hi, values.begin()+lo); }; sort(sort, 0, static_cast<int>(values.size()));}Komplexitet och avvägningar
Section titled “Komplexitet och avvägningar”| Mått | Kostnad | Förklaring |
|---|---|---|
| Bästa fall | O(n log n) |
Delning och sammanslagning sker ändå. |
| Genomsnitt | O(n log n) |
Logaritmiskt antal nivåer, linjärt arbete per nivå. |
| Sämsta fall | O(n log n) |
Varje nivå behandlar alla n element. |
| Extra minne | O(n) |
Implementationen använder en buffert. |
| Stabilitet | Stabil | Välj vänster halva vid lika värden. |
Mergesortering håller en god övre gräns för tidsåtgången men använder en extra buffert. Metoden passar när du behöver stabil sortering och konsekvent prestanda.
Vanliga misstag
Section titled “Vanliga misstag”- Att försöka slå ihop delar innan de är sorterade.
- Att blanda ihop inkluderande och exkluderande intervallgränser. Här används
[start, end). - Att glömma värden som blir kvar när ena halvan är slut.
- Att förbise buffertens minneskostnad.
Varför fungerar sammanslagningen?
Section titled “Varför fungerar sammanslagningen?”Båda halvorna är redan sorterade när de ska slås ihop. Nästa värde måste därför vara det minsta av de två första kvarvarande värdena. När ett värde har kopierats behöver det inte flyttas igen i den sammanslagningen. När en halva tar slut kopieras resten av den andra.
Minneskostnad
Section titled “Minneskostnad”En vanlig arraybaserad mergesort använder en extra buffert vars storlek växer med antalet objekt. Det är normalt bättre att återanvända en buffert än att skapa nya arrayer i varje rekursivt steg. Rekursionen behöver dessutom stackminne, men bufferten dominerar ofta minnesanalysen.
Stabilitet vid lika värden
Section titled “Stabilitet vid lika värden”När båda framvärdena är lika ska vi välja det från vänster halva först. Då behåller lika objekt sin tidigare ordning. Det spelar roll om objekten redan sorterats efter ett annat fält.