Összefésüléses rendezés

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.

Összefésüléses rendezés
Példa összefésüléses rendezésre (szerző: Swfung8). A listát az algoritmus először egyelemű részekre osztja, majd minden listát a szomszédos listával hasonlít össze, hogy rendezze, és összeegyesítse a két szomszédos listát. Végül minden elemet rendez és összeegyesít az algoritmus.
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

Algoritmus

Egy összefésüléses rendezés működése:

1. A rendezetlen lista n egyelemű allistára való osztása, melyeket rendezettnek tekint az algoritmus.
2. 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 TopDownMergeSort(A, B, length(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 $2^{i}$ 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[32]; 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

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 $O(n\log n)$. Ha egy n elemű lista rendezésének ideje $T(n)$, akkor $T(n)=2T({\frac {n}{2}})+n$ 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 $(n-2)\lceil \log _{2}n\rceil +1$, ami $n\log _{2}n-n+1$ és $n\log _{2}n+n+O(\log _{2}n)$ közt van. 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 $n\alpha$-val kevesebb a legrosszabb esetinél, ahol $\alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0{,}2645.$

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 $O(n\log n)$, 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 $O(n)$ 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:

• (Kronrod 1969) 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 $O(1)$ mutató tárolásához. $O(n\log n)$ időhatárt értek el, de az algoritmus nem stabil.
• Számos kísérlet történt helyben történő összefésülő algoritmusra, mely egy összefésülő rendezéssel összekapcsolható, helyben történő összefésülő rendezést adva. Itt a „helyben történő” tágítható „logaritmikus veremhelyet igénylő”-re, mivel a normál összefésüléses rendezés ennyi helyet igényel saját veremhasználatának. Geffert et al. kimutatták, hogy helyben történő stabil összefésülés lehetséges $O(n\log n)$ idő alatt konstans mennyiségű ideiglenes tárhellyel, de az algoritmus összetett, és magasak a konstans tényezők: n és m elemű tömbök egyesítéséhez $5n+12m+o(m)$ mozgatás is szükséges lehet. A bonyolult algoritmus egyszerűbbé és könnyebben megérthetővé vált. Bing-Chao Huang és Michael A. Langston egyértelmű lineáris idejű algoritmust („helyben történő praktikus összefésülés”) írtak le egy rendezett lista egyesítésére fix mennyiségű további helyigénnyel. Mindketten felhasználták Kronrod és társai munkáját. Az egyesítés lineáris időben történik konstans tárhelyszükséglet mellett. Az algoritmus átlagos futásideje kevesebb mint kétszer hosszabb az egyszerű összefésüléses rendezési algoritmusoknál, és $O(n)$ további ideiglenes memóriaegységet tud használni. Bár az algoritmus a gyakorlatban gyorsabb, bizonyos listák esetén instabil. De hasonló koncepciók meg tudták oldani e problémát is. További helyben történő algoritmus például az $O((n+m)\log(n+m))$ futásidejű és stabil SymMerge. Egy ilyen algoritmus komplexitása a nem linearitmikus, de mégis kvázilineáris $O(n(\log n)^{2})$.
• Sok külső rendezés több allistára osztó összefésüléses rendezést használ, ideális esetben annyira, hogy az egyesítésükkor a jelenleg feldolgozott oldalhalmazhoz még elég a fő memória.
• Modern stabil lineáris és helyben történő összefésülés-változat a blokk-összefésüléses rendezés, mely egyedi értékeket használ ideiglenes tárhelyként.
• A tárhelyköltség bináris keresésekkel és forgatásokkal ${\sqrt {n}}$-re csökkenthető. Ezt használja a C++ STL könyvtár és a quadsort.
• Másoláscsökkentő lehetőség az új információmezők kulcshoz (m eleméhez) rendelése. Ez a kulcsok és a kapcsolódó információk (a kulcsok) rendezett listába kapcsolására szolgál. A rendezett listák egyesítése ezután a kapcsolati értékek változtatásával folytatódik rekordmozgatás nélkül. Egy csak kapcsolatot tartalmazó mező általában kisebb a teljes rekordnál, így kevesebb helyet használ. Ez általános rendezési módszer, nem korlátozódik az összefésüléses rendezésre.
• A helyköltség $n/2$-re csökkentésére egyszerű mód a bal és a jobb oldal teljes szerkezetkénti kezelése, m bal oldalának ideiglenes helybe tétele, majd hogy az egyesítés az egyesített kimenetet m-be helyezze. Ekkor jobb az ideiglenes hely egyesítésen kívüli foglalása, egyszeri foglalást lehetővé téve. A korábban említett sok másolás is megszűnik, mivel a visszatérés előtti utolsó 2 sor fölössé válik.

Használata szalagos tárhelyekkel

Az összefésüléses rendezés nagy adathalmazok rendezését tették lehetővé a korai, kis memóriával rendelkező számítógépeken. Az adatokat mágnesszalagon tárolták, és azt kezelő rendszerek, például IBM 729 rendszerek dolgozták fel.

Egy külső összefésüléses rendezés hasznos lemez- vagy szalagmeghajtók esetén, ha az adat nagy az elsődleges tárnak. A külső rendezésen bemutatható a lemezekkel való működés. Egy általános szalagmeghajtós rendezés 4 szalagot használ. A be-/kimenet sorozatban történik (kivéve a visszatéréseket az áthaladások végén. Egy minimális megvalósításban csak 2 puffer és néhány programváltozó van.

A szalagokat A-tól D-ig elnevezve, ahol A-n van az eredeti adat, illetve 2 pufferrel az algoritmus hasonlít az alulról felfelé építkező megvalósításra, szalagmeghajtópárokat használva tömbök helyett. Az alapalgoritmust az alábbiak írják le:

1. A párjainak egyesítése, kétrekordos allisták írása C-re és D-re felváltva
2. C és D kéttagú allistáinak egyesítése felváltva A-ra és B-re.
3. A és B 4 tagú allistáinak egyesítése felváltva C-re és D-re
4. E lépések ismétlése rendezettségig $\log _{2}n$ lépésben.

Rövid sorozatokkal való kezdés helyett gyakran hibrid algoritmust használnak, ahol először sok adat kerül a memóriába, belső rendezést hajt végre hosszú sorozatot adva, majd ezeket a kimenetbe osztja el. Ez sok korai átmenetet elkerül. Például egy 1024 tagú belső sorozat 9-cel csökkenti a lépésszámot. A belső rendezés ezért gyakran nagy tömbökkel történik. Továbbá vannak módszerek az elérhető memóriánál nagyobb kezdeti sorozatok létrehozásához. Ezek egyike, Knuth bináris minimális kupacon alapuló snowplow algoritmusa a memóriánál átlagosan kétszer hosszabb sorozatokat ad.

Kis többletköltséggel ez módosítható háromszalagossá. $O(n\log n)$ futásidő érhető el 2 sorral, egy sorral és egy veremmel vagy 3 veremmel. $k>2$ szalaggal és $O(k)$ memóriaelemmel a szalagműveletek száma $O(\log k)$-szor csökkenthető ${\frac {k}{2}}$ irányú egyesítő algoritmussal.

A meghajtóhasználatot a polifázisos összefésüléses rendezés optimalizálja.

Optimalizáció

Csempézett összefésüléses rendezés véletlen egészeken. A vízszintes tengely az indexet, a függőleges az egészet jelenti.

Modern számítógépeken a referenciahely fontos lehet a szoftveroptimalizációban a többszintű memóriahierarchiák miatt. Gyorsítótárbiztos változatokat is javasoltak, ahol a műveletek a gyorsítótári mozgatást minimalizálják. Például a csempézett összefésüléses rendezés leállítja a résztömbök bontását, ha S méretű tömböket ért el, ahol S a processzor gyorsítótárában elférő adatelemek száma. E résztömböket helyben történő algoritmussal, például beillesztéses rendezéssel rendezik a memóriacserék számának csökkentéséhez, a normál összefésüléses rendezést a hagyományos rekurzív módon hajtja végre. Ez jobb teljesítményt mutatott gyorsítótár-optimalizációval rendelkező gépeken.(LaMarca & Ladner 1997)

Párhuzamos egyesítésű rendezés

Az összefésüléses rendezés jól párhuzamosítható az „oszd meg és uralkodj!” elv miatt Számos különböző párhuzamos változat jött létre az évek folyamán. Egyes párhuzamos változatok a sorozatos felülről lefelé haladó összefésülő algoritmushoz kapcsolódnak, míg másoknak ettől eltérő általános szerkezetük van, és K irányú összefésülést használnak.

Párhuzamos rekurzióval

A sorozatos összefésüléses rendezés két szakasszal írható le: a felosztásos és az egyesítő fázissal. Az első sok rekurzív hívásból áll, melyek azonos osztási folyamatot hajtanak végre, míg a részsorozatok triviálisan rendezettek (legfeljebb 1 eleműek). Egy intuitív megközelítés ezek párhuzamosítása. Az alábbi pszeudokód a fork és a join kulcsszavakkal működő párhuzamos rekurziós módszert írja le:

// A tömb lo–hi közti (exkluzív) elemeinek rendezése.
algorithm mergesort(A, lo, hi):
    if lo+1 < hi:  // 2 vagy több elem.
        mid := ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

Ez az algoritmus a sorozatosnak triviális módosítása, és nem jól párhuzamosít. Így gyorsulása nem jelentős. Munkaideje $\Theta (n)$, ami csak $\Theta (\log n)$-szer jobb a sorozatosnál. Ez főképp a sorozatos egyesítés miatt van, mely a szűk keresztmetszetet jelenti a párhuzamos végrehajtásokban.

Párhuzamos összefésülésű rendezés

Jobb párhuzamosság érhető el párhuzamos összefésülő algoritmussal. Cormen et al. egy bináris változatot mutatnak be, mely két rendezett részsorozatot egy rendezett kimenetbe egyesítenek.

Az egyik sorozatban (egyenlőtlen hossz esetén a hosszabban) kiválasztja a középső elemet. Helyzetét a másik sorozatban úgy határozza meg, hogy az elem beillesztése után a sorozat rendezett marad. Így ismert, hány elem kisebb a sorozatokból, és a kiválasztott elem helyzete a kimeneti sorozatban kiszámítható. A kisebb és nagyobb elemekből álló részsorozatra az algoritmus végrehajtása ismét párhuzamosan történik az alapeset eléréséig.

Az alábbi pszeudokód módosított párhuzamos összefésülő rendezést mutat párhuzamos összefésülő algoritmussal (forrás: Cormen et al.).

/**
 * A: Bemenet
 * B: Kimenet
 * lo: alsó határ
 * hi: felső határ
 * off: eltolás
 */
algorithm parallelMergesort(A, lo, hi, B, off):
    len := hi - lo + 1
    if len == 1 then
        B[off] := A[lo]
    else let T[1..len] be a new array
        mid := ⌊(lo + hi) / 2⌋ 
        mid' := mid - lo + 1
        fork parallelMergesort(A, lo, mid, T, 1)
        parallelMergesort(A, mid + 1, hi, T, mid' + 1) 
        join 
        parallelMerge(T, 1, mid', mid' + 1, len, B, off)

A legrosszabb eset rekurzív számításához az ismétlődő hívásoknak csak egyszer kell megtörténniük párhuzamosságuk miatt, így:

$$T_{\infty }^{\text{sort}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+\Theta \left(\log(n)^{2}\right).$$

E függvény megoldása:

$$T_{\infty }^{\text{sort}}=\Theta \left(\log(n)^{3}\right).$$

E párhuzamos összefésülő algoritmus párhuzamossága ${\textstyle \Theta \left({\frac {n}{(\log n)^{2}}}\right)}$, az előző algoritmusénál sokkal nagyobb. Egy ilyen rendezés gyors stabil sorozatos rendezéssel és gyors sorozatos összefésüléssel kis tömbök egyesítésére való alapesettel jól működhet.

Párhuzamos többirányú összefésüléses rendezés

Nem mindig megfelelő az összefésüléses rendezés kétirányú összefésülésre való korlátozása, hiszen sokszor $p>2$ processzor érhető el. Jobb megközelítés lehet k irányú összefésülést használni, mely ennek általánosítása, ahol k rendezett sorozat egyesítése történik. Ez alkalmas egy PRAM rendezési algoritmusát.

Alapötlet

Párhuzamos többirányú összefésüléses rendezés 4 processzoron ($t_{0}$–$t_{3}$).

Egy n elemű rendezetlen sorozat esetén a cél a sorozat rendezése p processzorral. Ezek egyenlően vannak elosztva a processzorok közt és helyben rendezve sorozatos rendezési algoritmussal. Így a sorozat $\lceil {\frac {n}{p}}\rceil$ hosszú $S_{1},\cdots ,S_{p}$ sorozatokból áll.

Az egyes sorozatokat többsorozatos/elosztó kiválasztásra használják. $j=1,\cdots ,p$-re az algoritmus meghatározza a $v_{j}$ elválasztóelemeket, melyek rangja $k={\frac {jn}{p}}$. Ezután a $v_{1},\cdots ,v_{p}$ helyzeteit bináris kereséssel határozzák meg, így az $S_{i}$ tovább bomlik p részsorozatra ($S_{i,1},\cdots ,S_{i,p}$, ahol $S_{i,j}:=\{x\in S_{i}|{\text{rang}}(v_{j-1}<{\text{rang}}(x)\leq {\text{rang}}(v_{j})\}.$

Majd az $S_{1,i},...,S_{p,i}$ elemei, vagyis minden ${\frac {n(i-1)}{p}}.$ és ${\frac {ni}{p}}.$ közti elem az i. processzorhoz kerülnek, melyek $S_{i}$ egészén el vannak osztva. Így minden processzor rendezett sorozatok sorozatát kapja. Hogy az elválasztó elemek rangja, k globálisan lett megválasztva, két fontos tulajdonságot ad: Egyrészt k úgy lett megválasztva, hogy minden processzor ${\frac {n}{p}}$ elemen működik hozzárendelés után. Az algoritmus tökéletesen kiegyensúlyozott. Másrészt az i. processzorhoz tartozó összes elem kisebb vagy egyenlő az i+1.-hez tartozó összes elemnél. Így minden processzor helyben végrehajt p irányú egyesítést, a részsorozatokból rendezett sorozatot adva. Így nem kell további p irányú egyesítés, az eredményeket a processzorszám sorrendjében kell egymás mellé helyezni.

Többsorozatos választás

A legegyszerűbb változatban p egyenlően p processzor közt elosztott rendezett $S_{1},...,S_{p}$ sorozat, valamint k rang esetén a feladat x megtalálása, melynek globális rangja k az összes sorozatban. Ez felhasználható minden $S_{i}$ felosztására két részre egy adott $l_{i}$ felbontó indexnél, ahol az egyik rész csak x-nél kisebb, a másik csak x-nél nagyobb elemeket tartalmaz.

Az alábbi sorozatos algoritmus a szétválasztások indexeit adja ki, vagyis az $l_{i}$-ket az $S_{i}$ sorozatokban, ahol $S_{i}[l_{i}]$ globális rangja k-nál kisebb, és $\mathrm {rang} (S_{i}[l_{i}+1])\geq k$.

algorithm msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int):
    for i = 1 to p:
	(l_i, r_i) = (0, |S_i|-1)
    while there exists i: l_i < r_i:
	// elem kijelölése S_j[l_j], .., S_j[r_j] közt, egyenlő eloszlású véletlen j választása
	v := pickPivot(S, l, r)
	for i = 1 to p:
	    m_i = binarySearch(v, S_i[l_i, r_i]) // sorozatosan
	if m_1 + ... + m_p >= k: // m_1+ ... + m_p v globális rangja
	    r := m  // vektor-hozzárendelés
	else
	    l := m 
    return l

A komplexitáselemzéshez a PRAM modell választható. Ha az adat egyenlően oszlik el minden p-nél, a binarySearch p-szeri végrehajtásának futásideje ${\mathcal {O}}\left(p\log \left({\frac {n}{p}}\right)\right).$ A várható ismétlési mélység ${\mathcal {O}}\left(\log \left(\textstyle \sum _{i}|S_{i}|\right)\right)={\mathcal {O}}(\log n)$ ahogy a gyors választásnál is. Így a teljes várható futásidő ${\mathcal {O}}\left(p\log {\frac {n}{p}}\log n\right).$

Párhuzamos többirányú összefésüléses rendezésre alkalmazva az algoritmusnak párhuzamosan kell futnia, hogy minden ${\textstyle {\frac {ni}{p}}}$ rangú felezőelem, ahol $i=1,\cdots ,p$ egyidejűleg legyen megtalálható. Ezen elemek ezután minden sorozat p részre osztására felhasználható, az összes futásidő ${\mathcal {O}}\left(p\,\log {\frac {n}{p}}\log n\right)$.

Pszeudokód

Alább a párhuzamos többirányú összefésüléses rendezés teljes pszeudokódja van, ha határszinkronizáció a többsorozatos választás előtt és után, így minden processzor meg tudja találni az elválasztó elemeket és a sorozatfelbontást.

/**
 * d: rendezetlen tömb
 * n: elemszám
 * p: processzorszám
 * return Sorted Array
 */
algorithm parallelMultiwayMergesort(d : Array, n : int, p : int):
    o := new Array[0, n]                         // kimeneti tömb
    for i = 1 to p in parallel:                // minden processzor párhuzamosan
        S_i := d[(i-1) * n/p, i * n/p] 	         // n/p hosszú sorozat
	sort(S_i)                                // lokális rendezés
        synch
	v_i := msSelect([S_1,...,S_p], i * n/p)          // ni/p globális rangú elem
        synch
	(S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // s_i felbontása részsorozatokra
	o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i)  // egyesítés és kimenethez rendelés
    return o

Elemzés

Először minden processzor rendezi a hozzá tartozó ${\frac {n}{p}}$ elemet ${\mathcal {O}}\left({\frac {np}{\log {\frac {n}{p}}}}\right)$ komplexitású algoritmussal. Ezután az elválasztóelemeket kiszámítják ${\mathcal {O}}\left(p\,\log {\frac {n}{p}}\log n\right)$ idő alatt. Végül minden p tagú elemet párhuzamosan egyesítik a processzorok ${\mathcal {O}}(\log p{\frac {n}{p}})$ idő alatt sorozatos p irányú egyesítéssel. Így a futásidő ${\mathcal {O}}\left({\frac {n}{p}}\log {\frac {n}{p}}+p\log {\frac {n}{p}}\log n+{\frac {n}{p}}\log p\right).$

Gyakorlati használata

A többirányú összefésüléses rendezés nagy párhuzamosíthatósága miatt nagyon skálázható, lehetővé téve sok processzor használatát. Ez lehetőséget ad nagy mennyiségű adat rendezésére, például számítógépklaszterek esetén. Mivel az ilyen rendszerekben a memória jellemzően nem korlátozó tényező, az összefésüléses rendezés helykomplexitásbeli hátránya elhanyagolható. Azonban más tényezők fontosak az ilyen rendszerekben, melyeket nem vesznek figyelembe PRAM modellnél. Például ilyen tényezők a memóriahierarchia, a gyorsítótárban el nem férő adat és a processzorok közti adatcsere során fellépő kommunikációs költségek, melyek korlátozó tényezők lehetnek, ha közös memórián már nem érhetők el az adatok.

Sanders et al. tömeges szinkronpárhuzamos algoritmust mutattak be többszintű többirányú összefésüléses rendezésre, mely p processzort $r\ p'$ méretű csoportra bont. A processzorok először helyben rendeznek. Szemben az egyszintű többirányú összefésüléses rendezéssel, e sorozatok r részre vannak osztva, és a megfelelő processzoorcsoportokhoz kerülnek. E folyamat ismétlődik e csoportokban, csökkentve a kommunikációt és elkerülve a sok kis üzenet okozta problémát. A valós hálózat szerkezete használható a processzorcsoportok meghatározására.

További változatok

Az összefésüléses rendezés volt az egyik első rendezési algoritmus optimális gyorsítással. Richard Cole alminta-algoritmust használt $O(1)$ idejű összefésüléshez. Más párhuzamos rendezési algoritmusok hasonló vagy jobb időkorlátokat tudnak elérni alacsonyabb konstansokkal. Például 1991-ben David Powers párhuzamosított gyors rendezést és ehhez kapcsolódó gyökrendezést írt le, mely $O(\log n)$ idő alatt tudott futni CRCW PRAM-on n processzorral implicit felosztással. Powers kimutatta, hogy Batcher biton rendezésének csatornázott változatának futásideje $O((\log n)^{2})$ pillangó-rendezőhálózaton, ami azonban a gyakorlatban gyorsabb, mint az $O(\log n)$ rendezés PRAM-on, és részletesen leírja a rejtett költségeket az összehasonlítás, a gyök- és a párhuzamos rendezés esetén.

Összehasonlítás más rendezésekkel

A Perl 5.8-ban az összefésüléses rendezés lett az alapértelmezett rendezőalgoritmus a gyors rendezés után. In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted. The Linux kernel uses merge sort for its linked lists. A Python Tim-rendezést használ, mely az összefésüléses és a beillesztéses rendezés keveréke, ezenkívül a Java SE 7 (nem primitív típusú tömböknél), az Android és a GNU Octave alapértelmezett rendezőalgoritmusa lett.

Fordítás

Ez a szócikk részben vagy egészben a Merge sort című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

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 [3]
• 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.)

További információk

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