#include <stdio.h>
//this program is edited by 200624101101杨振平
//this paper's edited time is Nov 7th,2008
//define count of array
#define N 9
//main function
void main()
{
//declare MergeSort function
void MergeSort(int r[ ], int r1[ ], int s, int t);
//initial the array r[] which require to sort
int r[N]={9,8,7,6,5,4,3,2,1};
//define the new array r1[] to store the sort elements
int r1[N];
//call the MergeSort function
MergeSort(r,r1,0,N-1);
//print the sort result array
for(int i=0;i<N;i++)
printf("%d/t",r1[i]);
}
//implement the MergeSort function
void MergeSort(int r[ ], int r1[ ], int s, int t)
{
//declare the Merge function
void Merge(int r[ ], int r1[ ], int s, int m, int t);
//declare variables
int m,rtemp[N];
//apply the recurrence general formula
if (s==t) r1[s]=r[s];
else {
m=(s+t)/2;
//merge and order the first half son array
MergeSort(r, r1, s, m);
//merge and order the last half son array
MergeSort(r, r1, m+1, t);
//use a temp array to story the new sort array r1's information
for(int i=0;i<N;i++)
rtemp[i]=r1[i];
//merge the temp array to be an ordered sort array which will be the
//result of the new array r1,otherwise r1 will recover itself.
//merge two ordered son array
Merge(rtemp, r1, s, m, t);
}
}
//implement the Merge function
void Merge(int r[ ], int r1[ ], int s, int m, int t)
{
//declare flag variables and init
int i,j,k;
i=s;
j=m+1;
k=s;
//get the min value between r[i] and r[j] to store into r1[k]
while (i<=m && j<=t)
{
if (r[i]<=r[j]) r1[k++]=r[i++];
else r1[k++]=r[j++];
}
//if the first array has not done all,then ending is handled
if (i<=m) while (i<=m)
r1[k++]=r[i++];
//if the second array has not done all,then ending is handled
else while (j<=t)
r1[k++]=r[j++];
}
