merge sort

Angol

Főnév

merge sort (tsz. merge sorts)

1. (informatika) összefésülő rendezés

---

A merge sort (magyarul: összefésüléses rendezés) egy hatékony, oszd meg és uralkodj (divide and conquer) elven működő összehasonlító rendező algoritmus. Stabil és garantáltan ${\textstyle O(n\log n)}$ időben rendezi az elemeket.

---

Hogyan működik a merge sort?

1. Oszd meg: A bemeneti tömböt két közel egyenlő részre bontja.
2. Urald: Rekurzívan rendezze a két rész tömböt.
3. Összefésül: Az így kapott két rendezett tömböt egyesítve egyetlen rendezett tömböt hoz létre.

---

Részletes lépések

• Ha a tömb mérete 1 vagy 0, akkor az már rendezett.
• Két rendezett rész tömböt egyesítünk úgy, hogy összehasonlítjuk az elemeket és sorban illesztjük őket egy új tömbbe.
• Az egyesítés lineáris időben történik.

---

Példa

Bemenet: ${\textstyle 38,27,43,3,9,82,10}$

• Osztás: ${\textstyle 38,27,43}$ és ${\textstyle 3,9,82,10}$
• Rendezés rekurzívan mindkettőn, majd összeolvasztás.
• Végül rendezett tömb: ${\textstyle 3,9,10,27,38,43,82}$

---

Időbonyolultság

• Átlagos és legrosszabb eset: ${\textstyle O(n\log n)}$
• Legjobb eset: ${\textstyle O(n\log n)}$
• A logaritmikus szorzó a rekurzív osztás miatt, az ${\textstyle n}$ a fésülés lineáris költsége miatt.

---

Előnyök és hátrányok

Előnyök	Hátrányok
Stabil rendezés	Többlet memóriaigény (extra tömb)
Garantált ${\textstyle O(n\log n)}$ idő	Lassabb, mint az in-place algoritmusok bizonyos esetekben
Jó párhuzamosíthatóság	Nem in-place (nem az eredeti tömbben dolgozik)

---

Összefoglalás

Fogalom	Leírás
Merge sort	Oszd meg és uralkodj algoritmus, két rendezett rész egyesítése
Idő:	Garantált ${\textstyle O(n\log n)}$ idő
Memória:	Többlet memória használata szükséges

További információk

• merge sort - Szótár.net (en-hu)
• merge sort - Sztaki (en-hu)
• merge sort - Merriam–Webster
• merge sort - Cambridge
• merge sort - WordNet
• merge sort - Яндекс (en-ru)
• merge sort - Google (en-hu)
• merge sort - Wikidata
• merge sort - Wikipédia (angol)