Merge sort

Merge sort je sortiranje spajanjem sortiranih nizova. To je algoritam koji radi na principu podeli i osvoji(divide and conquer). Razvio ga je von Neumann 1945. godine. Ovaj sort je pogodan za sortiranje na nekom spoljasnjem memorijskom medijumu

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.

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

Za n=8 i niz 44, 55, 12, 42, 94, 18, 6, 67 dobija se:

• 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.

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

Za n=8 i niz 44, 55, 12, 42, 94, 18, 6, 67 dobija se:

evo jednog gif-a koji ceo postupak lepo objasnjava :

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

nazad

literatura uzeta sa spa2 vezbi i http://www.wikipedia.org/