本文章的代码使用jetbrains公司旗下的的Clion编写，操作系统位macOS Ventura(13.2.1). 代码没有在dev-c++测试过（dev-c++可能会有相关的空格问题）
李春葆书
//
// Created by 魏志杰 on 2023/7/25.
//
#include "stdio.h"
#include "stdlib.h"
#define Max 100
#define before printf("排序前")
#define after printf("排序后")
#define newline printf("\n")
#define print printf("%6d", R[i].key)
#define printA printf("%6d",A[i])
#define Array int A[]={5,7,2,5,9,6,-42,1,67,2,3};
//begin merge sort
typedef struct {
int key;
int data;
} SqType;
//归并排序的基本思路是首先将R[0 n-1]看成是n个长度为1的有序表，将相邻的有序子表成对归并，得到n/2的长度为2的有序子表，然后再将这些有序子表成对归并
//得到n/4个长度为4的有序子表，如此反复，得到一个长度为n的有序子表
void Merge(SqType R[], int low, int mid, int high) {
//将R[low mid] 和R[mid+1 high]两个相临的有序表归并为一个有序表
SqType *R1;
//k 是R1的的下标 ，i，j 分别为第1，2子表的下标
int i = low, j = mid + 1, k = 0;
R1 = (SqType *) malloc((high - low + 1) * sizeof(SqType));
while (i <= mid && j <= high) //在第1子表和第二子表均未扫描完时循环
if (R[i].key <= R[j].key) { //将第1子表的元素放入R1中
R1[k] = R[i];
i++;
k++;
} else {
R1[k] = R[j]; //将第2子表的元素放入R1中
j++;
k++;
}
while (i <= mid) { //将第1子表剩余元素放入R1中
R1[k] = R[i];
i++;
k++;
}
while (j <= high) { //将第2子表剩余元素复制R1中
R1[k] = R[j];
j++;
k++;
}
for (k = 0, i = low; i <= high; k++, i++)
R[i] = R1[k]; //将R1复制回R中
free(R1); //释放R1所占的空间
}
void MergePass(SqType R[], int length, int n) { //一趟二路归并
int i;
for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length) //归并length长度的两相邻子表
Merge(R, i, i + length - 1, i + 2 * length - 1);
if (i + length - 1 < n) //余下两个子表，后者长度小于length
Merge(R, i, i + length - 1, n - 1); //归并这两个子表
}
void MergeSort(SqType R[], int n) {
int length;
for (length = 1; length < n; length = 2 * length)
MergePass(R, length, n);
}
int main() {
SqType R[Max];
Array;
for (int i = 0; i < 10; i++)
R[i].key = A[i];
before;
for (int i = 0; i < 10; i++)
print;
newline;
MergeSort(R, 10);
after;
for (int i = 0; i < 10; i++)
print;
}
代码结果如下
