right|thumb|Animacija sortiranja spajanjem. Sortirani elementi su predstavljeni tackama.
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 thumb|right|300п|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 - 2lg n + 1), što je između (n lg n - n + 1) i (n lg n + n + O(lg n)).The worst case number given here does not agree with that given in Knuth's Art of Computer Programming, Vol 3. The discrepancy is due to Knuth analyzing a variant implementation of merge sort that is slightly sub-optimal
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 thumb| 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: 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.Selection sort. Knuth's snowplow. Natural merge.
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