Szerkesztő:Barfe/Összefésüléses rendezés

---

Összefésüléses rendezés
Példa összefésüléses rendezésre (szerző Swfung8). First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.
Kategória	rendezési algoritmus
Adatstruktúra	tömb
Legrosszabb időbonyolultság	$O(n\log n)$
Legjobb időbonyolultság	$\Omega (n\log n)$ tipikus, $\Omega (n)$ természetes változat
Átlagos idő bonyolultság	$\Theta (n\log n)$
Legrosszabb tár bonyolultság	$O(n)$, segédváltozóval további $O(n)$, láncolt segédlistával további $O(1)$
Optimális	igen

A számítástechnikában a merge sort (gyakran egybeírva, mint mergesort ) hatékony, általános célú, az összehasonlító rendezések sorába tartozó rendezési algoritmus. Legtöbbször stabil rendezést valósít meg, vagyis az egyenlő elemek sorrendje a kimeneten ugyanaz, mint a bemeneten. Az oszd meg és uralkodj-elvű összefésüléses rendezés algoritmusát Neumann János 1945-ben gondolta ki. Az alulról felfelé építkező összefésülések részletes leírását és elemzését Goldstine és Neumann közölte, már 1948-ban.

Források

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
• Katajainen (1996). „Practical in-place mergesort”. Nordic Journal of Computing 3 (1), 27–40. o. [2011. augusztus 7-i dátummal az eredetiből archiválva]. ISSN 1236-6064. (Hozzáférés: 2009. április 4.)  . Also Practical In-Place Mergesort. Also [1]
• Knuth, Donald. Section 5.2.4: Sorting by Merging, Sorting and Searching, 2nd, The Art of Computer Programming, Addison-Wesley, 158–168. o. (1998). ISBN 0-201-89685-0 
• Kronrod (1969). „Optimal ordering algorithm without operational field”. Soviet Mathematics - Doklady 10, 744. o.  
• LaMarca (1997). „The influence of caches on the performance of sorting”. Proc. 8th Ann. ACM-SIAM Symp. On Discrete Algorithms (SODA97), 370–379. o.  
• Skiena, Steven S.. 4.5: Mergesort: Sorting by Divide-and-Conquer, The Algorithm Design Manual, 2nd, Springer, 120–125. o. (2008). ISBN 978-1-84800-069-8 
• Sun Microsystems: Arrays API (Java SE 6). (Hozzáférés: 2007. november 19.)
• Oracle Corp.: Arrays (Java SE 10 & JDK 10). (Hozzáférés: 2018. július 23.)

Külső hivatkozások

• Animated Sorting Algorithms: Merge Sort a Wayback Machine-ben (archiválva 2015. március 6-i dátummal)– grafikus bemutató
• Open Data Structures - Szakasz 11.1.1 - Merge Sort, Pat Morin

Kategória:Divide et impera (informatika) Kategória:Számítógép-programozás Kategória:Algoritmusok Kategória:Rendezési algoritmusok