归并排序本质上是将一个无序数据集分割成许多个只包含一个元素的集，然后不断地将这些小集合并，直到一个新的大有序集生成。在以下介绍的实现方法中，data最初包含size个无序元素，并放在单块连续的存储空间中。因为归并过程需要额外的存储空间，所以函数要为合并过程分配足够的内存。在函数返回后，最终通过合并得到的有序数据集将会拷贝回data。
归并排序最关键的部分是如何将两个有序集合并成一个有序集。这部分工作交由函数merge完成。它将data中i到j之间的数据集与j+1到k之间的数据集合并成一个i到k的有序数据集。
最初，ipos和jpos指向每个有序集的头部。只要数据集中还有元素存在，合并过程就将持续下去。如果数据集中没有元素，进行如下操作：如果一个集合没有要合并的元素，那么将另外一个集合中要合并的元素全部放到合并集合中。否则，首先比较两个集合中的首元素，判断哪个元素要放到合并集合中，然后将它放进去，接着根据元素来自的集合移动ipos或jpos的位置（如图4），依此类推。
现在我们来看看mgsort中如何来处理递归。在初次调用mgsort时，i设置为0，k设置为size-1。首先，分割data，此时j处于数据中间元素的位置。然后，调用mgsort来处理左边分区（从i到j）。左边的分区继续递归分割，直到传入mgsort的一个分区只包含单个元素。在此过程中，i不再小于k，因此调用过程终止。在前一个mgsort的过程中，在分区的右边也在调用mgsort，处理的分区从j+1到k。一旦调用过程终止，就开始归并两个数据集。总的来说，以这种递归方式继续，直到最后一次归并过程完成，此时数据就完全排好序了。
将数据集不断地对半分割，在分到每个集合只有一个元素前，需要lgn级分割（n为要排序的元素个数）。对于两个分别包含q和p个元素的有序集来说，归并耗费的时长为O（p+q），因为产生了一个合并的集，必须遍历两个集的每个元素。由于对应每个lgn级的分割，都需要遍历n个元素合并该集，因此归并排序的时间复杂度为O（nlgn）。又因为归并排序需要额外的存储空间，所以必须要有两倍于要排序数据的空间来处理此算法。
示例：归并排序的实现
/*mgsort.c*/
#include <stdlib.h>
#include <string.h>
#include "sort.h"
/*merge 合并两个有序数据集*/
static int merge(void *data, int esize, int i, int j, int k, int (*compare)(const void *key1,const void *key2))
{
char *a = data,
*m;
int ipos ,jpos,mpos;
/*初始化用于合并过程中的计数器*/
ipos = i;
jpos = j+1;
mpos = 0;
/*首先，为要合并的元素集分配空间*/
if((m = (char *)malloc(esize * ((k-i)+1))) == NULL)
return -1;
/*接着，只要任一有序集有元素需要合并，就执行合并操作*/
while(ipos <= j || jpos <=k)
{
if(ipos > j)
{
/*左集中没有元素要合并，就将右集中的元素放入目标集（合并集）*/
while(jpos <= k)
{
memcpy(&m[mpos * esize],&a[jpos * esize],esize);
jpos++;
mpos++;
}
continue;
}
else if(jpos > k)
{
/*右集没有要合并的元素，就将左集中的元素放入目标集（合并集）*/
while(ipos <= j)
{
memcpy(&m[mpos * esize],&a[ipos *esize],esize);
ipos++;
mpos++;
}
continue;
}