归并排序实现

归并排序，分治法，将一个无序的数组，不断二分，对两边数组进行排序，在通过递归的方式，将两个排过序的数组合并（关键）。

当子数组只有一个值时，即可进行合并。

代码如下：

#include 
     
      using namespace std;const int MAXN = 100;int A[MAXN] = {0,5,2,4,7,1,3,2,6};void Megre(int p,int q,int r){    int b[r-p+1];    int c[r-p+1];    int i = 1;    int j = 1;    int w;    w = 1;    for (int x = p;x<=q;x++)        b[w++] = A[x];    w = 1;    for (int x = q+1;x<=r;x++)        c[w++] = A[x];    w = p;    while (w <= r)    {        if (j > r-q||(b[i] < c[j]&&i <= q-p+1))        {            A[w] = b[i];            i++;        }        else        {            A[w] = c[j];            j++;        }        w++;    }}void Megre_sort(int p,int r){    if (p < r)    {        int q = (p + r) / 2;        Megre_sort(p, q);        Megre_sort(q + 1, r);        Megre(p, q, r);    }}int main(){    Megre_sort(1,8);    for (int i = 1;i<=8;i++)        printf("%d ",A[i]);    printf("\n");    return 0;}