머지 소트

#include <stdio.h>

#define SIZE 100

void merge(int initList[], int mergedList[], int i, int m, int n)

{

int j,k,t;

j = m+1;

k=i;

while(i<=m&&j<=n)

{

if(initList[i] <= initList[j])

mergedList[k++] = initList[i++];

else

mergedList[k++] = initList[j++];

}

if(i>m)

for(t=j;t<=n;t++)

mergedList[t] = initList[t];

else

for(t=i;t<=m;t++)

mergedList[k+t-i] = initList[t];  

}

void mergePass(int initList[], int mergedList[], int n , int s)

{

int i,j;

for(i = 1; i <=n-2*s+1;i+=2*s)

merge(initList, mergedList, i, i+s-1,i+2*s-1);

if(i+s-1<n)

merge(initList, mergedList, i, i+s-1,n);

else

for(j=i;j<=n;j++)

mergedList[j] = initList[j];

}

void msort(int a[], int n)

{

int s= 1;

int extra[SIZE];

while(s<n)

{

mergePass(a,extra,n,s);

s*= 2;

mergePass(extra,a,n,s);

s*=2;

}

}

void main()

{

int before[] = {0,5,4,3,2,1,0};

int i,k;

k = sizeof(before)/sizeof(int);

msort(before,k-1);

for(i = 0 ; i<k;i++)

printf("%d ",before[i]);

}