归并算法是将两个或两个以上的有序表组合成一个新的有序表，它的原理是：假设初始序列含有n个记录，则可以看成是n个有序子序列，两两归并，得到[n/2]个有序子序列，再次归并……不断重复直至归并到长度为n的有序序列，这样的排序方法称为2路归并排序，
算法：归并算法的递归与非递归形式
。实例一：递归形式的2路归并算法
#define MAXSIZE 4int data[MAXSIZE] = {2,1,0,3};/** 功能：将from数组min到max-1下标数据排好序，最后的结果是to[min]...to[max-1]* 输入：1.待排序的数组；2.排好序的数组；3.相关位置设定* 输出：无*/void merge(int from[],int to[],int min,int m,int max){ /*将from[]数组两侧元素排序放在to[]上，直至一侧"溢出"*/ int i = min , j = m+1; while(min<=m && j<=max) { if(from[min]< from[j]) to[i++] = from[min++]; else to[i++] = from[j++]; } /*由于子序列已经排好序，当上面的循环结束时，将还没"溢出"的一侧剩余元素直接赋给后面的to[]*/ if(min<= m) for(int k =0; k<=m-min; k++) to[i+k] = from[min+k]; if(j<= max) for(int k = 0; k<= max-j; k++) to[i+k] = from[j+k];}/** 功能：不断分组归并* 输入：1.待排序的数组；2.排好序的数组；3.相关位置设定* 输出：无*/void mSort(int from[],int to[],int min,int max){ if(min == max) // 不断分组，直至拷贝了一份原数组 to[min] = from[max]; else { int m = (min+max)/2; int temp[MAXSIZE]; // 创建一个新的数组来存储排序的子序列 mSort(from,temp,min,m); // 此时中间下标变为最大下标 , temp数组递归后为下一层的要megre的to数组 mSort(from,temp,m+1,max); // 此时中间下标+1变为最小下标 merge(temp,to,min,m,max); // 分到不能再分就开始不断归并 }}void print(int *data){ for(int i = 0; i< MAXSIZE; i++) printf("%d ",data[i]); printf("\n");}void main(int argc, char* argv[]){ print(data); mSort(data,data,0,MAXSIZE-1); print(data);}打印结果：
由程序可以看出，每分组一次就要创建一个临时存放数据的数组，这无疑会降低性能，所以可以采用非递归形式的归并算法，
电脑资料
《算法：归并算法的递归与非递归形式》(http://meiwen.anslib.com)。<喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGJyPgo8L3A+CjxwPsq1wP22/qO6t8e13bnp0M7KvbXEMsK3uemyosvjt6g8L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;">#include "stdio.h" #include "malloc.h"#define MAXSIZE 8int data[MAXSIZE] = {5,2,1,7,6,4,0,3};/** 功能：归并排序，自下而上，不采取递归方式，而是通过算法自下而上* 输入：待排序数组，数组元素个数* 输出：无*/void merge_sort(int *list, int length){ int i, left_min, left_max, right_min, right_max, next; int *tmp = (int*)malloc(sizeof(int) * length); // 由此至终都是和这个动态分配的数组打交道 for (i = 1; i< length; i *= 2) // 当i = 1时代表要归并的序列大小为1，依次类推 { /*当前大小的序列需要归并的次数，通过改变left_min来移动*/ for (left_min = 0; left_min< length - i; left_min = right_max) { right_min = left_max = left_min + i; // 序列切分为两半后相关位置设定 right_max = right_min + i; if (right_max >length) right_max = length; next = 0; /*将两组序列排序进入tmp直至一段"溢出"，尤其注意right_min的移动*/ while (left_min< left_max && right_min< right_max) tmp[next++] = list[left_min] >list[right_min] ? list[right_min++] : list[left_min++]; /*如果溢出的是右端，待排序的数组读取左端后面较大的数据*/ while (left_min< left_max) list[--right_min] = list[--left_max]; /*将之前存放到tmp的数组的数据继续读到数组*/ while (next >0) list[--right_min] = tmp[--next]; } } free(tmp);}void main(){ print(data); merge_sort(data,MAXSIZE); print(data);}打印结果基本同上
归并排序很重要的一个思想是，在归并的子序列是已经排好序的，这也是其中算法的关键。归并排序的时间复杂度是O(nlogn)，处理大量数据时性能远比简单排序算法要好，其中非递归归并算法的空间复杂度比递归归并算法的要小，整体性能较好。