====== Merge sort ======

**Merge sort** je sortiranje spajanjem sortiranih nizova. To je  algoritam koji radi na principu podeli i osvoji([[http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm|divide and conquer]]).
Razvio ga je [[http://en.wikipedia.org/wiki/John_von_Neumann|von Neumann]] 1945. godine.
Ovaj sort je pogodan za sortiranje na nekom spoljasnjem memorijskom medijumu

===Princip rada===
----

Postoje dve verzije ovog sorta:
  *__**verzija 1**__
Par najduzih neopadajućih podnizova se spaja (uparuje) i dobija se jedan neopadajući podniz.
Svakim prolazom se smanjuje broj neopadajućih podnizova.
==Kod:==
<code c>
void merge_arr(inta1,int a2,int b1,int b2,int *c,int*d){
intk1;
k1=a1;
while ((a1<=a2) && (b1<=b2))
if (c[a1]<c[b1]) d[k1++]=c[a1++];
else d[k1++]=c[b1++];
while (a1<=a2) d[k1++]=c[a1++];
while (b1<=b2) d[k1++]=c[b1++];
}

void dodeli(intp,intk, inta[], intb[]){
int i;
for(i=p;i<=k;i++) a[i]=b[i];
}

void merge(intn, intna[]){
inta1=0,a2,b1,b2=-1,k=1,nb[n],i;
a1=a2=0;
while ((na[a2]<na[a2+1])&&(a2<n-1)) a2++;
while(k){
if((b1=b2=a2+1)==n) k=0;
else {
while ((na[b2]<na[b2+1])&&(b2<n-1)) b2++;
merge_arr(a1,a2,b1,b2,na,nb);
dodeli(a1,b2,na,nb);
a2=b2;
}
}
}
</code>
Za n=8 i niz 44, 55, 12, 42, 94, 18, 6, 67 dobija se: 

{{merge1.jpg?400}}

  *__**verzija 2**__
Ako je niz duzine 0 ili 1, onda je niz vec sortiran, u suprotnom  delimo niz na pola, tj na dva podniza, i svaki podniz cemo sortirati rekurzivno ponovnom primenom merge sort-a. Onda spojimo ta dva podniza u jedan sortiran niz.
==Kod:==
<code c>
void dodeli(intp,intk, inta[], intb[]){
int i;
for(i=p;i<=k;i++) a[i]=b[i];
}

void merge2(intbegin,intend,inta[]){
intmid,temp[50];
if (begin<end) {
mid=(begin+end)/2;
merge2(begin,mid,a);
merge2(mid+1,end,a);
merge_arr(begin,mid,mid+1,end,a,temp);
dodeli(begin,end,a,temp);
}
}
</code>
Za n=8 i niz 44, 55, 12, 42, 94, 18, 6, 67 dobija se:

{{merge2.jpg?400}}

evo jednog gif-a koji ceo postupak lepo objasnjava :

{{merge-sort-example-300px.gif}}

Evo jos neki primer kad je neparan broj elemenata u nizu:

{{300px-merge_sort_algorithm_diagram.svg.png?300}}

[[ognjen.andric|nazad]]

literatura uzeta sa [[http://imi.pmf.kg.ac.rs/moodle/course/view.php?id=37|spa2 vezbi]] i http://www.wikipedia.org/