"sorteeritavaid" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

2. Sorteeri kumbki osa eraldi. 3. Kombineeri mõlemad osad kokku üheks sorteeritud massiiviks. • Olemuselt on see algortim rekursiivne ja toetub otseselt lähenemisele "Jaga ja valitse” (divide et impera). Rekursioonist väljudes ühendatakse massiivi osi järjest omavahel, saades nii üha pikemad sorteeritud lõigud. Vajab täiendavat mälu ajutiste massiivide tegemiseks (reaalselt sama palju kui on sorteeritavaid andmeid) • Keerukus: O(n log2n) nii halvimal kui ka keskmisel juhul. 11.3.1 Tugevad küljed • Stabiilne • Toimib hästi koos virtuaalse ja cache mäluga • Saab tööd jagada protsessorite vahel • Ei oma “raskeid” sisendandmeid • Hea sorteerida suurte andmete hulki, mis ei mahu mälus ära • Hea aeglaselt ligipääsetavate andmete sorteerimiseks, nt kõvaketas • Suurepärane nende andmete sorteerimiseks, mis jooksevad järjestikuliselt