一、算法实现
1.算法思想
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
核心步骤图示：
通俗来讲就是不断将序列平均分为左右两部分，当子序列元素个数为1时，将左右子序列不断进行合并，最后合并为一个完整的已经排好序的序列。
2.改进思路（循环实现）
既然归并排序的实现方法用到了递归思路，递归的深度会随着数据量的增多而加深，那么当数据量非常巨大时，就会出现递归超限的问题，对此问题可以采用循环实现归并排序的方法进行避免解决。
归并排序非递归（循环）实现思路：通过利用归并排序思想的逆序实现，即初始将序列分为n组，每组就只含有一个元素，然后进行两两归并，归并完成后，再将序列分为2个元素一组进行两两归并，每次分组组内元素个数都增加为原来的两倍再进行归并，当分组元素个数超过序列长度时即不足以划分至少一个分组时，归并结束，排序完成。
图示：
二、代码实现
1.完整代码
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<string.h> void MergeSort(int* array, int size);//归并排序 void _MergeSort(int* array, int left, int right, int* temp);//归并排序框架 void MergeDate(int* array, int left, int mid, int right, int* temp);//归并方法 void MergeSortNor(int* array, int size);//循环版本 void PrintArray(int* array, int size);//数组打印 void TestMergeSort();//测试函数 int main(){ TestMergeSort(); return 0; } void MergeSort(int* array, int size) {//归并排序 int* temp = (int*)malloc(sizeof(array[0]) * size); if (temp == NULL) {//申请失败 assert(0); return; } _MergeSort(array, 0, size, temp);//调用排序子函数 free(temp);//释放辅助空间 } void _MergeSort(int* array, int left, int right, int* temp) {//归并排序框架 if (right - left <= 1) {//序列内元素个数不超过一个开始回退进行下一步归并 return; } //1.将区间均分为两部分 int mid = (left + right) / 2; //2.递归排序左半侧和右半侧 _MergeSort(array, left, mid, temp); _MergeSort(array, mid, right, temp); //3.将左半侧和右半侧进行归并 MergeDate(array, left, mid, right, temp); //4.将temp内的有序序列拷贝到array中 memcpy(array + left, temp + left, sizeof(array[0]) * (right - left)); } void MergeDate(int* array, int left, int mid, int right, int* temp) {//归并方法 int begin1 = left;//左半侧区间 int end1 = mid; int begin2 = mid;//右半侧区间 int end2 = right; int index = left; while (begin1 < end1 && begin2 < end2) {//两个区间都不为空 if (array[begin1] < array[begin2]) {//将较小的元素依次放入temp temp[index++] = array[begin1++]; } else { temp[index++] = array[begin2++]; } } //将未放完的区间内的元素依次放入temp内序列之后 while (begin1 < end1) {//左半区间不为空 temp[index++] = array[begin1++]; } while (begin2 < end2) {//有半区间不为空 temp[index++] = array[begin2++]; } } void MergeSortNor(int* array, int size) {//循环版本 int* temp = (int*)malloc(sizeof(array[0]) * size); if (temp == NULL) {//申请失败 assert(0); return; } int gap = 1;//初始分组内元素个数 while (gap < size) { for (int i = 0; i < size; i += 2 * gap) {//注意i每次移动两个区间即两倍的gap int left = i;//归并序列左边界 int mid = left + gap;//归并两个小组的中间位置 int right = mid + gap;//归并序列右边界 if (mid > size) {//防止mid越界 mid = size; } if (right > size) {//防止right越界 right = size; } MergeDate(array, left, mid, right, temp);//进行归并 } memcpy(array, temp, size * sizeof(array[0]));//将归并好的序列拷贝回原空间 gap *= 2;//增加分组长度 } free(temp);//释放辅助区间 } void PrintArray(int* array, int size) {//数组打印 for (int i = 0; i < size; i++) { printf("%d ", array[i]); } } void TestMergeSort() {//测试函数 int array[] = { 9,7,3,1,8,10,4,6,2,5 }; int length = sizeof(array) / sizeof(array[0]); printf("排序前："); PrintArray(array, length); //MergeSort(array, length);//递归 MergeSortNor(array, length);//循环 printf("\n排序后："); PrintArray(array, length); }
2.测试结果
三、性能分析
1.归并排序的缺点在于需要O(n)的空间复杂度，归并排序的思想更多的是解决在磁盘中的外排序问题。
2.时间复杂度：
3.空间复杂度：
4.稳定性：稳定
