Sortare prin interclasare

Împarte lista în două jumătăți, sortează fiecare jumătate, apoi le unește într-o singură listă sortată.

cel mai bun caz Ω(n log n)
caz mediu Θ(n log n)
cel mai rău caz O(n log n)
memorie O(n)
stabil
necesită memorie suplimentară

Ce înseamnă acești termeni?

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ă

0 / 263 pași

Comparații Scrieri

Apasă pe redare: liniile arată cum crește costul în timpul sortării

Viteză 8 pași/s

Space: redă sau pauză. Săgețile stânga și dreapta: pas cu pas. Home și End: salt.

Î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.