（声明：文章全部图片均来自 传智播客 教师课件）归并排序是一种空间换时间的做法，排序的速度当然会提高很多，归并排序中会产生一个临时数组，这个临时数组用来把不断拆分到最后的有序数据进行合并，最后再把合并后的数据重新赋值给原数组，这样就实现了排序。主要分为以下三个步骤：
1、把原数组无限拆分到最少元素（直至剩余一个）如下图表示：
2、把拆分的两组数据合并到临时数组，如下图表示：
3、最后把临时数组中的值覆盖掉原始数组的值，整个过程就是下图这样的：
【实现代码】
代码语言：javascript复制#include <stdio.h>
void mergeArray(int arr[], int first, int mid, int last, int temp[])
{
// 两个有序序列合并后的长度
int length = 0;
// 记录拆分后左侧起始下标
int i = first;
// 记录拆分后右侧起始下标
int j = mid 1;
// 判断两个有序序列的下标是否到最后一个元素了
while (i <= mid && j <= last)
{
// 判断值哪个值小
if (arr[i] <= arr[j])
{
// 把小的值放到 temp 临时数组中
temp[length] = arr[i];
// 把小的数组的值下标向后移动
i ;
}
else
{
// 同上
temp[length] = arr[j];
j ;
}
// 每放进去一个值，记录temp数组长度的下标值就要 1
length ;
}
// 当上面循环结束时，一定还有一个数组没有遍历完，一个已经全部遍历完了
// 我们要把那个没有遍历完的数据剩下的元素放到临时数组中
while (i <= mid)
{
// 如果i的下标还没到最最后的位置，那么就循环把值赋给临时数组
temp[length] = arr[i];
length ;
i ;
}
while (j <= mid)
{
// 如果j的下标还没到最最后的位置，那么就循环把值赋给临时数组
temp[length] = arr[j];
length ;
j ;
}
for (i = 0; i < length; i )
{
// 有可能是从数组的中间位置开始拷贝的，这取决于传递进函数的参数
arr[first i] = temp[i];
}
}
void mergeSort(int arr[], int first, int last, int temp[])
{
if (first < last)
{
// 将数据分割成两份
int mid = (first last) / 2;
// 一次递归把两份左侧的数据和右侧的数据再次拆分
mergeSort(arr, first, mid, temp);
mergeSort(arr, mid 1, last, temp);
// 把拆分的数据进行排序（递归中，是从拆分到最后的2个或3个数进行排序）
mergeArray(arr, first, mid, last, temp);
}
}
int main(int argc, char* argv[])
{
int arr[11] = { 1, 21, 91, 284, 74, 57, 10, 38, 292, 28, 71 };
int temp[11];
mergeSort(arr, 0, 11 - 1, temp);
for (int i = 0; i < 11 - 1; i )
{
printf(“%d “, arr[i]);
}
return 0;
}
