Sortare prin interclasare
Împarte lista în două jumătăți, sortează fiecare jumătate, apoi le unește într-o singură listă sortată.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- da
- nu
Cel mai bun caz: cum crește timpul cu mărimea n a listei când intrarea e cea mai ușoară pentru acest algoritm.
Caz mediu: creșterea obișnuită a timpului. La n², de două ori mai multe valori cer cam de patru ori mai mult timp; n log n crește mai lent.
Cel mai rău caz: creșterea pe intrarea cea mai grea. Util când viteza nu are voie să scadă niciodată.
Memorie: câtă memorie suplimentară e necesară pe lângă listă. 1 înseamnă câteva variabile, n înseamnă o copie a listei.
Stabil: două valori egale își păstrează ordinea inițială. Contează când sortezi după un singur câmp al unei înregistrări.
Fără memorie suplimentară: sortează chiar în listă, fără o a doua listă.
- comparare
- mutare
- pe poziția finală
Încearcă: Alege o listă cu puține valori unice. Dintre două valori egale se ia întâi cea din jumătatea stângă, deci cele egale își păstrează ordinea.
Cum funcționează
Împarte lista iar și iar, până când fiecare bucată are o singură valoare, deci e deja sortată. Apoi unește bucățile două câte două: compară primele valori din cele două bucăți și o ia pe cea mai mică, până se termină. Rândul de sus din animație e spațiul suplimentar folosit la unire.
Când este o alegere bună
Când ai nevoie de o viteză care rămâne bună chiar și în cel mai rău caz, iar valorile egale trebuie să-și păstreze ordinea. Python și Java folosesc amândouă o variantă a acestui algoritm. Minusul e memoria suplimentară de care are nevoie.