简要步骤

将待排序列arr[n]看作是n个长度为1的有序序列，将相邻的有序序列合并成n/2个长度为2的有序序列，再将相邻的有序序列合并，直至最后得到一个长度为n的有序序列。

初始序列：{ 4, 6, 3, 0, 2, 5, 1 }

两个相邻序列合并过程详解：

性能分析

时间复杂度：归并排序的形式和二叉树类似，遍历次数就是二叉树的深度，所以时间复杂度是O( NlogN )；

空间复杂度：空间复杂度为O( N+logN )，如果使用非递归实现归并，则避免使用了深度为logN的栈空间，所以空间复杂度为O( N )；

稳定性：稳定。

代码

#include <stdio.h> /* * 归并操作 */ void Merge(int arr[], int left, int middle, int right) { //i是第一段序列的下标，j是第二段序列的下标，k是临时序列的下标 int i = left; int j = middle + 1; int k = 0; int num = right - left + 1; int temp[num]; while(i <= middle && j <= right) { if(arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } //如果第一段序列没扫描完，则将剩下的数据全部赋值到temp while(i <= middle) temp[k++] = arr[i++]; //如果第二段序列没扫描完，则将剩下的数据全部赋值到temp while(j <= right) temp[k++] = arr[j++]; //将临时序列temp中的数据赋值到原始序列 for(i = left, k = 0; k < num; i++, k++) arr[i] = temp[k]; } /* * 归并排序 */ void MergeSort(int arr[], int length) { int i = 0; for(int gap = 1; gap < length; gap *= 2) { //两两进行Merge操作 for(i = 0; i+2*gap-1 < length; i = i+2*gap) Merge(arr, i, i+gap-1, i+2*gap-1); //将最后没有gap长度的数据与前面一组数据进行Merge操作 if(i+gap-1 < length) Merge(arr, i, i+gap-1, length-1); } } int main() { int arr[] = {4,6,3,0,2,5,1}; int length = sizeof(arr)/sizeof(arr[0]); printf("排序前:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]); } MergeSort(arr, length); printf("\n排序后:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]); } return 0; }