Merge Sort

Algoritmul merge sort execută următorii paşi

1. Dacă lista este de lungime 0 sau 1, atunci este deja sortată. Altfel:
2. Împarte lista nesortată în două subliste aproximativ egale.
3. Sortează fiecare sublistă recursiv prin reaplicarea algoritmului merge sort.
4. Se interclaseaza cele două liste şi se obţine lista iniţială sortată.

#include "stdio.h"
#include "stdlib.h"

int *x;

void merge (int s,int d) {

int *y=(int *)malloc((d-s+1)*sizeof(int));
int i,j,k,m;
m=(s+d)/2;

for(i=s, j=m+1, k=0; i < =m && j < =d; k++)
if(x[i] < x[j])
   y[k]=x[i++];
else y[k]=x[j++];

for(; i < =m; k++)
   y[k]=x[i++];
for(; j < =d; k++)
   y[k]=x[j++];
for(k=0, i=s; k<d-s+1; k++)
   x[k+i]=y[k];
}


void ms (int i,int j) {

if(i < j) { ms(i,(i+j)/2);
  ms((i+j)/2+1,j);
  merge(i,j); }
}


int main()
{
int n, i;
scanf("%d",&n);
x=(int *)malloc(n*sizeof(int));

for(i=0; i < n; i++)
  scanf("%d",&x[i]);
printf("\n");

ms(0,n-1);
for(i=0; i < n ; i++)
   printf("%d ",x[i]);

return 0;

}