A számítástechnikában a merge sort (gyakran egybeírva, mergesort néven szerepel) 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.
Algoritmus Egy összefésüléses rendezés működése: A rendezetlen lista n egyelemű allistára való osztása, melyeket rendezettnek tekint az algoritmus. Allisták összefésülése új, rendezett allisták kiadásához, míg egy allista nem marad. Ez a rendezett lista. Felülről lefelé építkező algoritmus A felülről lefelé történő összefésüléses rendezést megvalósító C-szerű példakód indexeket használ az algoritmushoz, mely folyamatosan szétválasztja a listát, amíg az allistaméret 1 nem lesz, majd azokat rendezett listává egyesíti. A másolást az egyesítési irány ismétlési szintenkénti váltogatásával kerüli el (kivéve egy szintén elkerülhető egyszeri kezdeti másolást). Ennek megértésének megkönnyítéséhez tekinthető egy kételemű tömb. Elemei átkerülnek B tömbbe, majd vissza A-ba. 4 elem esetén az egyelemű listák elérésekor azok A-ból átkerülnek B-be, majd a következő szintben e kételemű sorozatok kerülnek A-ba. Ez a minta folytatódik minden ismétlődési szinttel. // „A” tömbben vannak a rendezendő elemek, „B” munkatömb. void TopDownMergeSort(A[], B[], n) { CopyArray(A, 0, n, B); // „A”-ból „B”-be való egyszeri másolás TopDownSplitMerge(A, 0, n, B); // B adatainak rendezése A-ba }
// A két sorozatra osztása, azok B-be rendezése, majd a sorozatok egyesítése B-ből A-ba // iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set). void TopDownSplitMerge(B[], iBegin, iEnd, A[]) { if (iEnd - iBegin <= 1) //legfeljebb 1 elemű sorozat esetén return; // tekintse rendezettnek // split the run longer than 1 item into halves iMiddle = (iEnd + iBegin) / 2; // iMiddle = középpont // A szakaszainak rendezése B-be TopDownSplitMerge(A, iBegin, iMiddle, B); // bal oldali szakasz rendezése TopDownSplitMerge(A, iMiddle, iEnd, B); // jobb oldali szakasz rendezése // az eredmény másolása B-ből A-ba TopDownMerge(B, iBegin, iMiddle, iEnd, A); } // bal fél: A[iBegin:iMiddle-1] // jobb fél: A[iMiddle:iEnd-1] // eredmény: B[iBegin:iEnd-1] void TopDownMerge(B[], iBegin, iMiddle, iEnd, A[]) { i = iBegin, j = iMiddle; // Amíg a bal vagy a jobb szakasz tartalmaz elemet… for (k = iBegin; k < iEnd; k++) { // Ha van bal oldali szakaszfej, mely a jobb oldalinál kisebb if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i += 1; } else { B[k] = A[j]; j += 1;
void CopyArray(A[], iBegin, iEnd, B[]) { for (k = iBegin; k < iEnd; k++) B[k] = A[k]; } Az egész tömböt a rendezi.
Alulról felfelé való megvalósítás A listát n allistából álló tömbnek tekintett C-szerű példakód alulról felfelé való összefésüléses rendezésre, mely az allistákat fésüli össze két puffer közt:
// „A”-ban vannak a rendezendő elemek, „B” munkatömb void BottomUpMergeSort(A[], B[], n) { // Az egyes 1 elemű listák már rendezettek. // Fokozatosan hozzon létre 2, 4, 8 stb. elemű rendezett listákat a teljes tömb rendezéséig. for (width = 1; width < n; width *= 2)
// „A” width hosszúságú listákkal rendelkezik. for (i = 0; i < n; i += 2 * width){ // Két sorozat egyesítése: A[i:i+width-1] és A[i+width:i+2*width-1] egyesítése B-be // vagy A[i:n-1] másolása B-be (ha i+width >= n) BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
// B-ben 2*width hosszú sorozatok vannak. // B másolása A-ba a következő iterációhoz. // Hatékonyabb lenne A és B szerepeinek cseréje. CopyArray(B, A, n); // A-ban vannak a 2width hosszú listák.
// A bal lista: A[iLeft:iRight-1]. // A jobb lista: A[iRight:iEnd-1]. void BottomUpMerge(A[], iLeft, iRight, iEnd, B[]) { i = iLeft, j = iRight; // Amíg valamely szakaszban vannak elemek… for (k = iLeft; k < iEnd; k++) { // Ha a bal lista feje létezik, és kisebb a jobb listáénál. if (i < iRight && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i += 1; } else { B[k] = A[j]; j += 1;
void CopyArray(B[], A[], n){for (i = 0; i < n; i++)A[i] = B[i];}
Listahasználó felülről lefelé való megvalósítás Pszeudokód felülről lefelé való algoritmushoz, mely a bemeneti listát triviális rendezettségig osztja kisebb allistákra, majd az allistákat egyesíti, miközben a láncon egyre feljebb halad.
function merge_sort(list m): // Alapeset. 0 vagy 1 elemű lista triviálisan rendezett. if length of m ≤ 1 then return m // Rekurzív eset. Először ossza fel a listát azonos méretű allistákra, melyek a lista két feléből állnak. Itt feltételezzük, hogy a listák 0-tól kezdődnek. var left := empty list var right := empty list for each x with index i in m do if i < (length of m)/2 then add x to left else add x to right // A két allista rekurzív rendezése. left := merge_sort(left) right := merge_sort(right) // A rendezett allisták egyesítése. return merge(left, right)
Itt a merge függvény egyesíti a bal és a jobb allistákat.
function merge(left, right): var result := empty list while left is not empty && right is not empty: if first(left) ≤ first(right): append first(left) to result left := rest(left) else: append first(right) to result right := rest(right) // A bal és a jobb részek pontosan egyikében maradhat elem: ezeket távolítsa el (az alábbi ciklusokból csak egybe lép az algoritmus). while left is not empty: append first(left) to result left := rest(left) while right is not empty: append first(right) to result right := rest(right) return result
Alulról felfelé haladó megvalósítás listákkal Az alulról felfelé haladó rendezési algoritmus pszeudokódja látható itt kis hivatkozástömbbel, ahol az array[i] vagy méretű listára hivatkozás, vagy nil. A node hivatkozás vagy csomópontra mutat. A merge függvény hasonlít a fenti példára: két rendezett listát egyesít, és üres listákat is kezel. Ez esetben a node-ot bemeneti paramétereire és kimenetére használja.
function merge_sort(node head) is // visszatérés üres lista esetén if head = nil then return nil var node array; initially all nil var node result var node next var int i result := head // csomópontok egyesítése while result ≠ nil do next := result.next; result.next := nil for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do result := merge(array[i], result) array[i] := nil // ne menjen a tömb végén túl if i = 32 then i -= 1 array[i] := result result := next // tömb egyesítése egy listába result := nil for (i = 0; i < 32; i += 1) do result := merge(array[i], result) return result
Elemzés bélyegkép|jobbra|Rekurzív összefésüléses algoritmus 7 egész rendezésére (felülről lefelé haladó rendezéssel).
n objektum rendezésében az összefésüléses rendezés átlagos és legrosszabb eseti teljesítménye . Ha egy n elemű lista rendezésének ideje , akkor az algoritmus definíciójából (az algoritmus két fele akkora listára való alkalmazása, valamint a két lista egyesítéséhez szükséges n lépés összege. Ez az „oszd meg és uralkodj” ismétlések főtételéből következik.
A legrosszabb esetben végzett összehasonlításokat a rendezési számok adják meg. Ezek értéke legfeljebb , ami és közt van.A legrosszabb esetben szereplő szám nem egyezik Donald Knuth Art of Computer Programming című könyvének 3. kötetével. Ennek oka, hogy Knuth egy kissé gyengébb összefésülésesrendezés-változatot elemez. Az összefésüléses rendezés legjobb esetben mintegy feleannyi ismétlést igényel a legrosszabb esetnél.
Nagy n és véletlenszerű bemeneti lista esetén az összefésüléses rendezés várható összehasonlítás-száma -val kevesebb a legrosszabb esetinél, ahol
Legrosszabb esetben az összefésüléses rendezés mintegy 39%-kal kevesebb összehasonlítást végez a gyors rendezés átlagos eseténél, mozgatásszáma , hasonlóan a gyors rendezés legjobb esetéhez.
A gyors rendezésnél hatékonyabb az összefésüléses rendezés, ha a rendezendő adat csak sorozatban érhető el hatékonyan, így népszerű az olyan nyelvekben, mint a Lisp, ahol az ilyen adatszerkezetek gyakoriak. Szemben a gyors rendezés egyes megvalósításaival, az összefésüléses rendezés stabil.
Az összefésüléses rendezés leggyakoribb megvalósítása nem helybe rendez, így a bemenet memóriamérete a rendezett kimenetnek fenntartandó (vö. lejjebb n/2 további helyet igénylő változatokhoz).
Természetes összefésüléses rendezés A természetes összefésüléses rendezés hasonlít az alulról felfelé építkezőre, de a természetesen előforduló rendezett részsorozatokat felhasználja. A monoton és a biton sorozatok is felhasználhatók, a listák hatékony adatszerkezetek erre (FIFO sorozatként vagy LIFO vermekként). Az alulról felfelé építkező összefésüléses rendezés feltételezi. hogy minden sorozat egyelemű. A gyakorlatban a véletlenszerű bemenet sok rövid, rendezett részsorozattal rendelkezik. Általában nincs annyi áthaladásra szükség, mivel kevesebb egyesítendő sorozat van. Legjobb esetben a bemenet már rendezett (vagyis egy sorozat), így a természetes összefésüléses rendezésnek csak egyszer kell áthaladnia az adaton. Sok gyakorlati esetben hosszú természetes sorozatok is vannak, ezeket használja ki a Tim-rendezésben is a természetes összefésüléses rendezés. Például:
Kezdet : 3 4 2 1 7 5 8 9 0 6 Sorozatok : (3 4)(2)(1 7)(5 8 9)(0 6) Összefésülés: (2 3 4)(1 5 7 8 9)(0 6) Összefésülés: (1 2 3 4 5 7 8 9)(0 6) Összefésülés: (0 1 2 3 4 5 6 7 8 9) Formálisan a természetes összefésüléses rendezés Runs-optimális, ahol Runs(L) L növekvő vagy csökkenő részsorozatainak számánál eggyel kisebb.
Torna–cserés kiválasztó rendezések használhatók a külső rendezőalgoritmusok kezdeti sorozatainak megadására.
Pingpong-összefésüléses rendezés A pingpong-összefésüléses rendezés 2 helyett 4 sorozatot egyesít. Ezeket két rendezett sorozatban fésüli össze, melyek egyesítve visszakerülnek a fő memóriába. Így nincs szükség a másolási műveletre, a mozgatások száma feleződik. Egy ilyen megvalósítás közkincsként jelent meg a WikiSortnál 2014-ben, melyet később a pasziánszrendezés optimalizációjának írtak le, és pingpongrendezésnek neveztek. A Quadsort 2020-ban vezette be e metódust quad merge néven.
Helyben történő összefésüléses rendezés Az összefésüléses rendezés egyik hátránya tömböknél az munkamemória-szükséglet. Számos módszert javasoltak ennek csökkentésére vagy a teljes helyben történő megvalósításra:
alternatív változatot javasolt konstans többlethelyszükséglettel. Katajainen et al. konstans mennyiségű munkamemóriát igénylő változatot javasoltak: elég tárhelyet a bemenet egy elemének, valamint további helyet mutató tárolásához. időhatárt értek el, de az algoritmus nem stabil.