Sortiranje spajanjem
Sortiranje spajanjem () 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:
 Podeliti nesortiran niz na n podnizova, od kojih svaki sadrži 1 element (niz od jednog elementa se smatra sortiranim).
 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 

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 - 2lg 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 

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 log2k puta, dobijemo istu rekurentnu relaciju. Ovo je tačno i ako k nije konstanta.

Upotreba sa trakama 

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:
 Spojiti podatke sa trake A; pišući podliste sa dva podatka naizmenično na C i D
 Spojiti podliste sa dva podatka sa C i D u podliste sa četiri podatka; pišući naizmenično na A i B
 Spojiti podliste sa četiri podatka sa A i B u podliste sa osam podataka; pišući naizmenično na C i D
 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. 

 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.

Reference

Literatura 

 . Also Practical In-Place Mergesort. Also

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}-

Сортирање поређењем
Стабилно сортирање
Алгоритми сортирања
Sortiranje spajanjem ( ) 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 godine . Detaljan opis i analiza sortiranja spajanjem odozdo-nagore su se pojavili u izveštaju koji su napisali Goldstine i Neumann još davne Algoritam Konceptualno , sortiranje spajanjem radi po sledecem principu : Podeliti nesortiran niz na n podnizova , od kojih svaki sadržielement ( niz od jednog elementa se smatra sortiranim ) . 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( prazna ) ili smatrajte je sortiranom i vratite je / / ( korišćenjem manje od ili jednako sprečava beskonačnu rekurziju za m dužine if length( m ) <= 1 return m / / inace , velicina niza je > pa ga delimo napodniza 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 ) >or length( right ) > 0 if length( left ) >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 .. dok se ne sortira ceo niz . * / for ( width = width < n ; width = * width ) { int i ; / * Niz A se sastoji od nizova dužine width * / for ( i = i < n ; i = i + * 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žinewidth * / / * 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žinewidth . * / } } 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 + } else { B[ j ] = A[ i1 ] ; i1 = i1 + } } } 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. predstavljapodniz ) , pa prirodno sortiranje spajanjem samo jednom prolazi kroz podatke . Analiza 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 ) =( 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 -g n + što je između ( n lg n - n +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 U najgorem slučaju , kod sortiranja spajanjem imamo 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 lokacija , dodatnih n lokacija se koriste često zato što je spajanjesortirana 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 ) =( n /2 ) + O( n ) ) i proširimo je log2k puta , dobijemo istu rekurentnu relaciju . Ovo je tačno i ako k nije konstanta . Upotreba sa trakama 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šćenjembafera i nekoliko promenljivih . Ako četiri trake označimo sa A , B , C , D , sa originalnim podacima na A , koristimo samobafera , tada je algoritam sličan implementaciji algoritma odozdo-nagore , i koristimo parove traka umesto nizova u memoriji . Opis algoritma glasi : Spojiti podatke sa trake A ; pišući podliste sa dva podatka naizmenično na C i D Spojiti podliste sa dva podatka sa C i D u podliste sa četiri podatka ; pišući naizmenično na A i B Spojiti podliste sa četiri podatka sa A i B u podliste sa osam podataka ; pišući naizmenično na C i D 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 sortiranjepodataka će uštedetiprolazaka . 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. 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 ,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 Perl8 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 odelemenata 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 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 . Reference Literatura \ . Also Practical In-Place Mergesort . Also 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 - Section1.1 - Merge Sort }- Сортирање поређењем Стабилно сортирање Алгоритми сортирања