Mergesort
Delar listan på mitten, sorterar varje halva och slår sedan ihop de två sorterade halvorna till en sorterad lista.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- ja
- nej
Bästa fall: hur tiden växer med listans storlek n när indata är den lättaste för den här algoritmen.
Genomsnitt: hur tiden brukar växa med n. Med n² tar dubbla antalet värden ungefär fyra gånger så lång tid. n log n växer mycket långsammare.
Värsta fall: tillväxten på den svåraste indatan. Viktigt när hastigheten aldrig får sjunka.
Minne: hur mycket extra minne som behövs utöver listan. 1 betyder några variabler, n betyder en kopia av listan.
Stabil: två lika värden behåller sin ursprungliga ordning. Viktigt när man sorterar poster efter ett fält.
Utan extra minne: sorterar inuti själva listan, utan en andra lista.
- jämförs
- flyttas
- på slutgiltig plats
Prova det här: Välj en lista med få unika värden. Av två lika värden tas det från vänstra halvan först, så lika värden behåller sin ordning.
Så fungerar det
Listan delas om och om igen tills varje bit har ett enda värde, och en sådan bit är redan sorterad. Sedan slås bitarna ihop parvis: jämför de första värdena i båda bitarna och ta det mindre, om och om igen. Den upplyfta raden i animationen är det extra utrymme som sammanslagningen behöver.
När det är ett bra val
När du behöver en hastighet som håller även i värsta fall, och lika värden måste behålla sin ordning. Både Python och Java använder en variant av mergesort. Nackdelen är det extra minne den behöver.