博主身为大二萌新，第一次学习数据结构，自学到排序的时候，对于书上各种各样的排序算法顿觉眼花缭乱，便花了很长的时间尽力把每一个算法都看懂，但限于水平有限，可能还是理解较浅，于是便将它们逐个地整理实现出来，以便加深理解。

归并排序就是通过将一个具有n个key记录的线性表，看成是具有n个有序子序列的排序叠加来实现对原有序列的排序的一种算法。它的中间状态就是将所有的子序列长度变为1，再将它们两两进行归并，得到长度为2或1的次级子序列，之后再进行两两归并，如此反复，直到得到一个长度为n的有序序列。这个过程包含了很多次的切分与归并，可以通过递归的方式来实现。归并排序的改进形式没有使用耗时较大的递归，而是改用了迭代法，这里我们先来讨论比较基础的递归法。

一共分成两个函数，一个是切分归并函数，另一个则是实现归并的函数。

话不多说，先粘贴我根据算法实现出来的源代码。

运行环境：win10&vs2015&.cpp或.c后缀文件形式

#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#include <string.h>
#include<cstdlib>#define OK 1
#define ERROR 0
#define MAXSIZE 100typedef int Status;typedef struct {//一个简单的线性链表结构int *Data;//线性链表的初址int length;
}SqList;/*线性链表初始化函数*/
Status InitSqList(SqList *S) {int n;printf("请输入需排序的数据个数：\n");scanf_s("%d", &n);getchar();//吸收换行符S->length = n;S->Data = (int*)malloc((n + 1)*sizeof(int));if (!S->Data)return ERROR;S->Data[0] = 0;//编写排序程序的小习惯(设立哨兵位,用于插入排序)for (int i = 1; i <= n; i++) {printf("第%d个数为:", i);scanf_s("%d", &S->Data[i]);getchar();//吸收换行符}return OK;
}/*归并排序的归并函数*/
void Merge(int SR[], int TR[], int i, int middle, int rightend) {//实际上这里的i也就是要排序合并的数组段的左起始点int j, k, l;for (k = i, j = middle + 1; i <= middle&&j <= rightend; k++) {if (SR[i] < SR[j])/*将SR中的元素按小到大的顺序存入TR,只需比较中点两侧对应下标元素大小*/TR[k] = SR[i++];elseTR[k] = SR[j++];}if (i <= middle) {/*若中点左边元素剩余,将剩余元素并入TR(注意这里并入只要按照顺序即可,因为SR已经排好序了)*/for (l = 0; l <= middle - i; l++)TR[k + l] = SR[i + l];}if (j <= rightend) {/*若中点右边元素剩余,将剩余元素并入TR*/for (l = 0; l <= rightend - j; l++)TR[k + l] = SR[j + l];}
}/*归并排序递归函数*/
void MSort(int SR[], int TR1[], int s, int t) {int middle;int TR2[MAXSIZE + 1];if (s == t)TR1[s] = SR[s];else {middle = (s + t) / 2;/*将SR分成以middle为界的两部分*/MSort(SR, TR2, s, middle);/*递归将SR[s,middle]归并为有序的数组TR2*/MSort(SR, TR2, middle + 1, t);/*递归将SR[middle+1,t]归并为有序的数组TR2*/Merge(TR2, TR1, s, middle, t);/*将上面的两部分分别有序的TR2归并为总体有序的TR1*/}
}/*总体调用排序函数*/
void MergeSort(SqList *S) {MSort(S->Data, S->Data, 1, S->length);
}int main()
{SqList S;InitSqList(&S);MergeSort(&S);printf("\n");for (int i = 1; i <= S.length; i++){printf("第%d个数为\t%d\n", i, S.Data[i]);}system("pause");return 0;
}

运行结果：

这里的递归过程我思考了很久才算是彻底想清楚，下面整理给大家，以供参考。

以严蔚敏老师的书上的数列为例：{49,38,65,97,76,13,27}

这些元素在前面代码中对应下标为{1,2,3,4,5,6,7}

上图为鄙人对递归函数执行过程的一部分进行的整理。退出(1)与(2)的递归步骤以后，执行的就是Merge(TR2,TR1,1,2,4)的归并排序函数了，就是将TR2[1...2]与TR2[3...4]归并到TR1[1...4](即上图Msort(SR,TR2,1,4)中的形参TR2)。

由此可见，所谓的将TR2排序归并到TR1的merge函数，在退到最外层递归以前，都是指排序归并到merge函数的形参TR1即实参TR2中。在最外层递归函数，才是将middle两侧的排好序的部分有序的TR2归并到真正的TR1中，获得最后的整体有序的排序结果。

另外的半部分的递归执行过程同理，在此就不进行赘述了。

这么一个看上去很简单的归并排序我竟然搞了这么久才懂，也是菜的不行，但想到自己每天能比之前强上那么一点点，就开心的不行呢。