Összefésülő rendezés (algoritmus)

Az összefésülő rendezés alapötlete, hogy eleve rendezett elemsorozatok aránylag egyszerűen vonhatók össze rendezett sorozattá. Az algoritmus lényege, hogy az elemeket két csoportba osztjuk, a csoportokat rendezzük (akár összefésülő rendezéssel), majd a kapott részeket összefésüljük.

Az összefésülés lényege, hogy a bemeneti sorozatok aktuális elemét nézve a kimeneti sorozatba mindig a kisebb kerül. Így egy összefésülés futásideje a kimeneti sorozat hosszával arányos.

Összefésülés forráskódja C++-ban:

   #include <queue>
   typedef std::queue<int> intq;
   intq merge( intq & a, intq & b ) {
      intq q;
      while ( ! a.empty() || ! b.empty() ) {
         if ( ! a.empty() && ( b.empty() || a.front() < b.front() )) {
            q.push( a.front() );
            a.pop();
         } else {
            q.push( b.front() );
            b.pop();
         }
      }
      return q;
   }

Ugyanez tömbökkel, C-ben:

   void merge(int a[], unsigned a_len, int b[], unsigned b_len, int c[]) {
     /* Feltesszük, hogy a c tömb hossza egyenlő az a és b tömbök hosszának összegével */
     unsigned a_index, b_index, c_index;

     a_index = 0; b_index = 0; c_index = 0;
     while (a_index < a_len || b_index < b_len) {
       if (b_index==b_len ||
           a_index<a_len && a[a_index] <= b[b_index]) {
         c[c_index] = a[a_index];
         a_index++;
       } else {
         c[c_index] = b[b_index];
         b_index++;
       }
       c_index++;
     }
     /* Ezen a ponton garantáltan a_index==a_len, b_index==b_len, c_index==a_len+b_len
        és a c tömb rendezett, ha a és b rendezettek voltak. */
   }

Az algoritmus szavakkal:

* Mindaddig amíg mindkét imput sor el nem fogy fut a ciklus.
* Ha az első sor elfogyott, a második sor következő elemét kell kivenni és a kimenő sorba illeszteni.
* Ha a második sor elfogyott, az első sor következő elemét kell kivenni és a kimenő sorba illeszteni.
* Ha mindkét sorban található még elem, akkor ha az első sorban található elem nagyobb vagy egyenlő, akkor azt kell kivenni és a kimenő sorba illeszteni.
* Ha mindkét sorban található még elem, akkor ha az második sorban található elem nagyobb, akkor azt kell kivenni és a kimenő sorba illeszteni.

Az algoritmus gyakorlati használatakor a valóságban nem csak két bemenő sort használunk, hanem több bemenő sort, amelyek mindegyikét egyszerre, egy menetben fésüljük össze.

Az algoritmus hátránya, hogy helyben nem végezhető, a szükséges (gyakran nem egyenlő méretű) részsorozatok megvalósítása bizonyos programnyelveken nem nyilvánvaló.

Előnye, hogy ha az adatszerkezetek rendelkezésre állnak (pl. fájlok, adatbáziskezelők esetén), az algoritmus nem igényel további (számottevő) adatterületet, ezért nagyon nagy (akár a memória méretét is meghaladó) sorozatokra is alkalmazható.

Pont ez a tulajdonsága tette népszerűvé a nagygépes korszakban a mágnesszalagos rendezéseknél, hiszen tipikusan kis memória, kevés vagy semmi disk kapacitás jellemezte ezt a kort nagy mágnesszalagos kapacitással.

Külön érdekesség, hogy az összefésülős rendezés ismét reneszánszát éli különleges igények esetén. A Google-nál gyakran használt módszer, mivel annyira nagy adatmennyiségek rendezése szükséges, amit más algoritmusokkal lényegesen kevésbé hatékonyan lehet csak elvégezni. Városi legendák szerint a Google állásinterjúin gyakori kérdés, hogy egy hatalmas adatmennyiséget meghatározó feladatban hogyan oldaná meg a jelölt a rendezést. A megoldás természetesen ez az algoritmus, így aki nem ismeri, nem is képes jól megoldani a feladatokat.