基本思想：将待排序元素分为大小一致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

1.将一个集合分成两个大小一致的2个子集合：

2.先对左右两边两个子集进行排序，需要再次分成两个更小的子集。分集合直到子数组的长度为1时停止递归。

3.对上诉子集合分别进行排序并合成大集合

代码：

1.对大集合不断划分成相等的两个小集合：mid=(right+left)/2,左边小集合为（left,mid），右边小集合为（mid+1,right）

void mergeSort(int A[],int left,int right) {if (left==right) {return;}if (left<right) {int mid = (right + left) / 2;mergeSort(A,left,mid);mergeSort(A,mid+1,right);}
}

2.分成直到子数组的长度为1时进行排序并合成大集合：范围是（left,right）

merge(A,left,right);

        2.1两个小的集合进行排序并合成大集合，比较左边集合和右边集合的第一个数据哪个小就放在第一个位置，以上诉例子为基础：排序（左边集合1 3 9和右边集合2 5 8）

1和2比，1小，放第一位，3和2比，2小放第二位，9和5比，5小放第三位，9和8比，8小放第四位，剩下的未放置的9直接跟在新集合的后面。

void merge(int A[], int left, int right) {//排序合并int n = right - left + 1;int *b=(int *)malloc(sizeof(int)* n);int i = 0, mid = (right + left) / 2;int l = left, k = mid + 1;while ((l<= mid) && (k <= right)) {if (A[l] < A[k]) {//左边集合跟右边集合的数进行比较，谁小谁放前面b[i++] = A[l++];}else {b[i++] = A[k++];}}if (l > mid) {//后面一个小分组还有剩余未处理的数for (k; k <= right; k++) {b[i++] = A[k];//直接放在新集合的后面}}if (k>right) {//前面小分组还有剩余未处理的数for (l; l <= mid;l++) {b[i++] = A[l];}}//再将b数组中的数据全部复制到A中for (int j = 0; j < n;j++) {A[left+j] = b[j];}free(b);
}

完整代码：

#include<stdio.h>
#include<malloc.h>//打印排序好的数组
void printfA(int A[], int n) {for (int i = 0; i < n; i++) {printf("%d ", A[i]);}printf("\n");
}void merge(int A[], int left, int right) {//排序合并int n = right - left + 1;int *b=(int *)malloc(sizeof(int)* n);int i = 0, mid = (right + left) / 2;int l = left, k = mid + 1;while ((l<= mid) && (k <= right)) {if (A[l] < A[k]) {b[i++] = A[l++];}else {b[i++] = A[k++];}}if (l > mid) {//后面一个小分组还有剩余未处理的数for (k; k <= right; k++) {b[i++] = A[k];}}if (k>right) {//前面小分组还有剩余未处理的数for (l; l <= mid;l++) {b[i++] = A[l];}}//再将b数组中的数据全部复制到A中for (int j = 0; j < n;j++) {A[left+j] = b[j];}free(b);
}void mergeSort(int A[],int left,int right) {if (left==right) {return;}if (left<right) {int mid = (right + left) / 2;mergeSort(A,left,mid);mergeSort(A,mid+1,right);merge(A,left,right);}
}int main() {int n;printf("请输入排序数字得个数：");scanf_s("%d",&n);int *A = (int*)malloc(sizeof(int)*n);printf("请输入排序得数字：");for (int i = 0; i < n;i++) {scanf_s("%d",&A[i]);}mergeSort(A,0,n-1);printfA(A, n);free(A);return 0;
}