Sortiranje spajanjem

Animacija sortiranja spajanjem. Sortirani elementi su predstavljeni tackama.

Sortiranje spajanjem (енгл. merge sort) je algoritam sortiranja baziran na poređenju, složenosti O(n log n). Većina implementacija daje stabilan niz, što znači da implementacija čuva redosled jednakih elemenata sa ulaza. Sortiranje spajanjem je "podeli pa vladaj" algoritam koji je izmislio Džon fon Nojman 1945. godine. Detaljan opis i analiza sortiranja spajanjem odozdo-nagore su se pojavili u izveštaju koji su napisali Goldstine i Neumann još davne 1948.

Algoritam

Konceptualno, sortiranje spajanjem radi po sledecem principu:

1. Podeliti nesortiran niz na n podnizova, od kojih svaki sadrži 1 element (niz od jednog elementa se smatra sortiranim).
2. U više navrata spajati podnizove sve dok se ne dobije novi podniz. Ovo ce biti sortiran niz.

Implementacija odozgo-nadole

Primer pseudokoda za algoritam spajanja odozgo-nadole koji koristi rekurziju da bi podelio niz na podnizove, i onda spaja podnizove tokom povratka iz rekurzije.

function merge_sort(list m)
    // ako je velicina promenljive 0 (prazna) ili 1, smatrajte je sortiranom i vratite je
    // (korišćenjem manje od ili jednako sprečava beskonačnu rekurziju za m dužine 0)
    if length(m) <= 1
        return m
    // inace, velicina niza je > 1, pa ga delimo na 2 podniza
    var list left, right
    var integer middle = length(m) / 2
    for each x in m before middle
         add x to left
    for each x in m after or equal middle
         add x to right
    // rekurzivno zovemo merge_sort() kako bismo dalje delili svaki podniz
    // dok veličina podniza ne postane 1
    left = merge_sort(left)
    right = merge_sort(right)
    // spajamo podniz vracen iz prethodnog poziva merge_sort()
    // i vracamo rezultujuci spojeni podniz
    return merge(left, right)

U ovom primeru, funkcija merge spaja levi i desni podniz.

function merge(left, right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) <= first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result

Implementacija odozdo-nagore

Primer C++ koda za algoritam spajanja odozdo-nagore:

/* niz A[] koji se sortira; B[] je pomocni niz */
BottomUpSort(int n, array A[n], array B[n])
{
  int width;

  /* pojedinacni elementi iz A su vec "sortirani". */

  /* Pravi podnizove dužine 2, 4, 8, 16... dok se ne sortira ceo niz. */
  for (width = 1; width < n; width = 2 * width)
    {
      int i;

      /* Niz A se sastoji od nizova dužine width */
      for (i = 0; i < n; i = i + 2 * width)
        {
          /* Spajamo: A[i:i+width-1] i A[i+width:i+2*width-1] u B[] */
          /* ili kopiramo A[i:n-1] u B[] (if(i+width >= n) ) */
          BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }

      /* Sad je pomocni niz B sacinjen od podnizova dužine 2*width */
      /* Kopiramo niz B u niz A za sledecu iteraciju */
      /* Efikasnija implementacija bi zamenila A i B*/
      CopyArray(A, B, n);
      /* Sad je niz A sacinjen od podnizova dužine 2*width. */
    }
}

BottomUpMerge(array A[], int iLeft, int iRight, int iEnd, array B[])
{
  int i0 = iLeft;
  int i1 = iRight;
  int j;

  /* Dok ima elemenata */
  for (j = iLeft; j < iEnd; j++)
    {
      /* Ako postoji pokazivac na levi kraj i ako je <= od postojeceg desnog */
      if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
        {
          B[j] = A[i0];
          i0 = i0 + 1;
        }
      else
        {
          B[j] = A[i1];
          i1 = i1 + 1;
        }
    }
}

Prirodno sortiranje spajanjem (Natural merge sort)

Ovo sortiranje je slicno sortiranju spajanjem odozdo-nagore osim što se svaki prirodan podniz (sortirana sekvenca) sa ulaza eksploatiše. U sortiranju spajanjem odozdo-nagore poletna tacka uzima da svaki podniz sadrži samo jedan element. U praksi, bilo koji ulaz ce imati mnogo kratkih podnizova koji su slucajno sortirani. U tipicnom slucaju, prirodnom sortiranju spajanjem možda neće biti potrebno onoliko prolazaka jer ima manje podnizova za spajanje. Na primer, u najboljem slucaju ulaz je vec sortiran (tj. predstavlja 1 podniz), pa prirodno sortiranje spajanjem samo jednom prolazi kroz podatke.

Analiza

Rekurzivni poziv algoritma za sortiranje 7 celih brojeva.

Za sortiranje n elemenata, složenost u prosecnom i najgorem slucaju je O (nlogn). Ako je vreme izvršavanja za niz dužine n T(n), onda rekurentna relacija T(n) = 2R(n/2) + n sledi iz definicije algoritma (primeni algoritam na dva niza cija je dužina polovina originalnog niza i dodaj n koraka za spajanje dva dobijena niza). Ovo sledi iz Master teoreme.

U najgorem slučaju, broj poređenja je manji ili jednak (n lg n - 2^lg n + 1), što je između (n lg n - n + 1) i (n lg n + n + O(lg n)).

Za veliko n i slučajno sortiran ulazni niz, očekivani broj poređenja je a·n manji nego u najgorem slučaju, gde je $\alpha =-10+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.$

U najgorem slučaju, kod sortiranja spajanjem imamo 39% manje poređenja nego što imamo kod kviksorta u prosečnom slučaju. U broju koraka, složenost u najgorem slučaju iznosi O (n log n)— ista složenost kao u najboljem slučaju kviksorta, a najbolji slučaj sortiranja spajanjem ima upola manje poređenja nego njegov najgori slučaj.

Najčešća implementacija sortiranja spajanjem koristi pomoćni niz za koji je potrebno alocirati prostor u memoriji (videti ispod verzije koje koriste samo n/2 dodatnog prostora).

Stabilno sortiranje u mestu je moguće ali komplikovanije i obično sporije, čak i ako algoritam takođe radi u vremenu O(n log n). Jedan način sortiranja u mestu je da se podnizovi spoje rekurzivno. Kao i standardno sortiranje spajanjem, sortiranje u mestu je takođe stabilno sortiranje. Stabilno sortiranje povezanih listi je jednostavnije. U ovom slučaju, algoritam ne koristi više prostora od onoga što se već koristi za predstavljanje liste, ali koristi O(log(k)) prostora za rekurzivne pozive.

Sortiranje spajanjem je efikasnije nego kviksort za neke vrste nizova ako se podacima koji treba da se sortiraju može efikasno prići jedino sekvencijalno i zbog toga je popularan u jezicima kao što je Lisp, gde su strukture podataka kojima se pristupa sekvencijalno veoma uobičajene. Za razliku od nekih (efikasnih) implementacija kviksorta sortiranje spajanjem je stabilno sortiranje sve dok se operacija spajanjem primenjuje kako treba.

Sortiranje spajanjem ima i neke nedostatke. Jedan od njih je korišćenje 2n lokacija, dodatnih n lokacija se koriste često zato što je spajanje 2 sortirana niza u mestu komplikovanije i potrebno je više poređenja i pomeranja. Uprkos korišćenju ovog prostora, algoritam i dalje obavlja dosta posla: sadržaj m se prvo kopira u left i right a kasnije u niz result za svaki poziv merge_sort (imena promenljivih se odnose na pseudokod). Alternativa ovom kopiranju je da se poveže novo polje informacije sa svakim ključem (elementi u m se zovu ključevi). Ovo polje će biti korišćeno kako bi se povezali ključevi i informacije u sortiranu listu (ključ i informacije vezane za njega se zovu ploče). Onda sledi spajanje sortiranih listi koje se odvija menjanjem vrednosti veze; nijedna ploča ne mora da se pomeri. Polje koje sadrži samo vezu će generalno biti manje u odnosu na čitavu ploču tako da će i manje prostora biti upotrebljeno.

Druga alternativa za smanjenje prostora na n/2 jeste da se održe left i right kao kombinovana struktura, da se kopira samo left deo niza m u pomoćni niz i da se preusmeri merge rutina kako bi se rezultat spajanja smestio u m. Sa ovom verzijom bolje je alocirati pomoćni niz izvan merge rutine, tako da je potrebna samo jedna alokacija. Suvišno kopiranje pomenuto u prethodnom pasusu je takođe smanjeno, jer je poslednji par linija pre naredbe return result (funkcija merge u pseudokodu) postao suvišan.

Sortiranje spajanjem se može izvršiti spajanjem više od dva podniza istovremeno koristeći n-way algoritam spajanja. Ipak, broj operacija je približno isti. Uzmimo na primer spajanje k podnizova istovremeno gde je zbog jednostavnosti k stepen dvojke. Rekurentna relacija postaje T(n) = k T(n/k) + O(n log k). (Poslednji deo proizilazi iz algoritma spajanja, kome je ako se primeni optimalno koristeći hip ili balansirano binarno stablo potrebno O (log k) vremena po elementu.) Ako posmatramo rekurentnu relaciju za obično sortiranje spajanjem (T(n) = 2T(n/2) + O(n)) i proširimo je log₂k puta, dobijemo istu rekurentnu relaciju. Ovo je tačno i ako k nije konstanta.

Upotreba sa trakama

Algoritmi sortiranja spajanjem omogućavaju da se velika količina podataka sortira na računarima sa malo RAM-a, što je bio slučaj kod starijih računara. Podaci su čuvani na magnetnim trakama i obrađivani na čitačima magnetne trake, kao što je IBM 729.

Spoljašnje sortiranje je praktično za rad sa diskovima i trakama kada su podaci koje treba sortirati preveliki da stanu u memoriju. Spoljašnje sortiranje objašnjava kako se sortiranje spajanjem implementira u disk drajv. Tipičan sort koristi četiri trake. Sav Ulaz/Izlaz je sekvencijalan. Minimalna implementacija je moguća korišćenjem 2 bafera i nekoliko promenljivih.

Ako četiri trake označimo sa A, B, C, D, sa originalnim podacima na A, koristimo samo 2 bafera, tada je algoritam sličan implementaciji algoritma odozdo-nagore, i koristimo parove traka umesto nizova u memoriji. Opis algoritma glasi:

1. Spojiti podatke sa trake A; pišući podliste sa dva podatka naizmenično na C i D
2. Spojiti podliste sa dva podatka sa C i D u podliste sa četiri podatka; pišući naizmenično na A i B
3. Spojiti podliste sa četiri podatka sa A i B u podliste sa osam podataka; pišući naizmenično na C i D
4. Ponavljati dok se ne dobije jedna lista koja sadrži sve podatke, sortirana za log2(n) prolazaka.

Umesto čitanja malo podataka, prvi prolaz će učitati dosta podataka u memoriju, napraviće unutrašnje sortiranje i na taj način omogućiti učitavanje velikog broja podataka i onda ih proslediti na izlaz. Ovim korakom se izbegavaju rani prolasci. Na primer, unutrašnje sortiranje 1024 podataka će uštedeti 9 prolazaka. Unutrašnje sortiranje je često veliko jer ima takvu prednost. Zapravo, postoje tehnike kojima se mogu produžiti početni prolasci u odnosu na dostupnu internu memoriju.

Sofisticiranije sortiranje spajanjem koje optimizuje prostor traka i diskova je uz pomoć sortiranja polifaznim spajanjem.

Optimizacija sortiranja spajanjem

Na savremenim računarima, lokalitet reference može biti od najveće važnosti u softverskoj optimizaciji, jer se koristi memorijska hijerarhija sa više nivoa. Verzije bazirane na korišćenju keša algoritma sortiranja spajanjem, čije su operacije posebno izabrane kako bi smanjile pomeranje stranica u i iz keš memorije mašine su bile predložene. Na primer, tiled merge sort algoritam prestaje da deli podnizove kada se dostignu podnizovi veličine S, gde je S broj elemenata podataka koji staju u keš procesora. Svaki od ovih podnizova se sortira koristeći algoritam za sortiranje koji radi u mestu kao što je sortiranje umetanjem, da bi se izbegle razmene u memoriji, i onda se kompletira normalno sortiranje spajanjem na standardni rekurzivni način. Ovaj algoritam je pokazao bolje performanse na mašinama koje imaju korist od optimizacije keša.

Kronrod 1969 je predložio alternativnu verziju sortiranja spajanjem koja koristi konstantni dodatni prostor. Ovaj algoritam je kasnije poboljšan..

Takođe, mnoge aplikacije spoljašnjeg sortiranja koriste formu sortiranja spajanjem pri čemu se ulaz deli na veći broj podlista, u idealnom slučaju na onaj broj za koji važi da bi njihovim spajanjem setovi strana koji se trenutno obrađuju stali u glavnu memoriju.

Paralelno procesiranje

Sortiranje spajanjem dobro paralelizuje zbog korišćenja zavadi-pa-vladaj metoda. Paralelna implementacija je prikazana u pseudokodu u trećem izdanju ove knjige Cormen, Leiserson, and Stein's Introduction to Algorithms. Ovaj algoritam koristi paralelni algoritam spajanja ne samo da bi paralelizovao rekurzivnu podelu niza već i za operaciju spajanja. Dobro funkcioniše u praksi kada se kombinuje sa brzim stabilnim sekvencijalnim sortiranjem kao što je sortiranje umetanjem i brzim sekvencijalnim spajanjem kao osnovnim slučajem za spajanje malih nizova. Sortiranje spajanjem je bio jedan od prvih algoritama za sortiranje gde je postignuta optimalna brzina, sa Richard Cole-om koji je koristio pametni algoritam da obezbedi složenost O(1). Drugi sofisticirani algoritmi za paralelno spajanje mogu da dostignu isto ili bolje granično vreme sa nižom konstantom. Na primer, 1991 David Powers je opisao paralelizovani kviksort (i sa tim u vezi radix sort) koji mogu da funkcionišu u vremenu O(log n) na CRCW PRAM sa n procesora koji obavljaju implicitno deljenje.

Poređenje sa drugim algoritmima sortiranja

Iako hipsort ima iste vremenske granice kao i sortiranje spajanjem zahteva samo T(1) pomoćnog prostora za razliku od sortiranja spajanjem koje zahteva T(n), i on je često brži u praktičnim primenama. Na tipičnim savremenim arhitekturama, efikasne kviksort implementacije generalno bolje funkcionišu od sortiranja spajanjem kada treba sortirati nizove bazirane na RAMu. S druge strane, sortiranje spajanjem je stabilno sortiranje, bolje paralelizuje i efikasnije je kada treba pristupiti sekvencijalnim medijima kojima se sporo pristupa. Sortiranje spajanjem je često najbolji izbor kada treba sortirati povezanu listu: u ovoj situaciji relativno je lako implementirati sortiranje spajanjem tako da bi ono zahtevalo samo T(1) dodatnog prostora, a spor nasumični pristup povezane liste čini da neki drugi algoritmi (kao što je kviksort) rade loše, a drugi (kao što je hipsort) ne rade uopšte.

Od Perl 5.8 verzije, sortiranje spajanjem je standardni algoritam sortiranja (to je bio kviksort u ranijim verzijama). U Javi, metodi Arrays.sort() koriste sortiranje spajanjem ili izmenjeni kviksort u zavisnosti od tipova podataka i za efikasnost implementacije prelaze na sortiranje umetanjem kada manje od 7 elemenata niza treba da se sortiraju. Python koristi timsort, drugačije izmenjeno sortiranje spajanjem i sortiranje umetanjem koji je postao standardni algoritam sortiranja za Java SE 7, i na platformi Android platform.

Korisnost u online sortiranju

Operacija spajanja u sortiranju spajanjem je korisna u online sortiranju gde se niz koji treba da bude sortiran prima deo-po-deo, umesto sve odjednom na početku. U ovoj aplikaciji, sortira se svaki novi deo koji se primi koristeći bilo koji algoritam za sortiranje, a onda se spaja u naš do sada sortiran niz koristeći operaciju spajanja. Ipak, ovaj pristup može biti skup i prostorno i vremenski ako su delovi koji se primaju mali u poređenju sa sortiranim nizom - bolji pristup u ovom slučaju je da se elementi ubace u binarno stablo pretrage onako kako se primaju.

Literatura

• Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). „Practical in-place mergesort”. Nordic Journal of Computing. 3. стр. 27—40. ISSN 1236-6064. Архивирано из оригинала 7. 8. 2011. г. Приступљено 4. 4. 2009. . Also Practical In-Place Mergesort. Also [1]
• Knuth, Donald (1998). „Section 5.2.4: Sorting by Merging”. Sorting and Searching. The Art of Computer Programming. 3 (2nd изд.). Addison-Wesley. стр. 158—168. ISBN 978-0-201-89685-5. 
• Kronrod, M. A. (1969). „Optimal ordering algorithm without operational field”. Soviet Mathematics - Doklady. 10. стр. 744. 
• LaMarca, A.; Ladner, R. E. (1997). „The influence of caches on the performance of sorting”. Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA97): 370—379. 
• Microsystems, Sun. „Arrays API”. Приступљено 19. 11. 2007. 
• Sun Microsystems. „java.util.Arrays.java”. Приступљено 19. 11. 2007. 

Spoljašnje veze

• Animated Sorting Algorithms: Merge Sort – graphical demonstration and discussion of array-based merge sort
• Dictionary of Algorithms and Data Structures: Merge sort
• Mergesort applet with "level-order" recursive calls to help improve algorithm analysis
• Open Data Structures - Section 11.1.1 - Merge Sort