代码思路：

这里实现的是稳定的从小到大排序；

将需要排序的数组分为长度为gap的组（gap为1,2,4,····gap小于等于数组的总长度）

对于长度为gap的数组，对半分成两组（由于这两组是分组长度为gap/2时的分组，所以组内是有序的），将这两组使用merge()函数进行合并排序

对于末尾长度不足gap但大于gap/2的数组使用merge()函数合并排序，但是参数发生一定的变化

对于末尾长度小于或等于gap/2的分组，由于其组内是有序的，因此暂不予理会

循环到gap大于n时，跳出循环，判断是否有小于gap/2的分组，如果有，将其与等于gap/2的分组合

并排序

#include
     
      #include
      
       using namespace std;int a[100];void sort1(int *a, int n);int main(){    int n;    while (cin >> n)    {        for (int i = 0; i < n; i++)            cin >> a[i];        sort1(a, n);        for (int i = 0; i < n; i++)            cout << "  " << a[i];        cout << endl;    }}void merge(int *a, int s1, int e1, int e2){
    //合并排序，s1，e1, e2分别为分组的开始坐标，中间坐标和结尾坐标    int i, j, k = 0;    int *b = (int *)malloc((e2 - s1 + 1) * sizeof(int));    for (i = s1, j = e1 + 1; i <= e1 && j <= e2;)    {        if (a[i] > a[j])        {            b[k++] = a[j];            j++;        }        else        {            b[k++] = a[i];            i++;        }    }    while (i <= e1)    {        b[k++] = a[i];        i++;    }    while (j <= e2)    {        b[k++] = a[j];        j++;    }    for (i = s1, j = 0; i <= e2; i++, j++)    {        a[i] = b[j];    }}void sort1(int *a, int n){    int gap;    for (gap = 1; gap <= n; gap *= 2)    {        int i;        for (i = 1; i * gap - 1 < n; i++)        {            merge(a, (i - 1) * gap, (i - 1) * gap + gap / 2 - 1, i * gap - 1);        }        if (n % gap > gap / 2)        {            merge(a, (i - 1) * gap, (i - 1) * gap + gap / 2 - 1, n - 1);        }    }    if (n % (gap / 2))    {        merge(a, 0, gap / 2 - 1, n - 1);    }}