归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针达到序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

//将有序数组a[]和b[]合并到c[]中void MemeryArray(int a[], int n, int b[], int m, int c[]){	int i, j, k;	i = j = k = 0;	while (i < n && j < m)	{		if (a[i] < b[j])			c[k++] = a[i++];		else			c[k++] = b[j++]; 	}	while (i < n)		c[k++] = a[i++];	while (j < m)		c[k++] = b[j++];}

可以看出合并有序数列的效率是比较高的，可以达到O(n)。 解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？ 可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过 先递归的分解数列，再合并数列就完成了归并排序。

//将有二个有序数列a[first...mid]和a[mid...last]合并。void mergearray(int a[], int first, int mid, int last, int temp[]){	int i = first, j = mid + 1;	int m = mid,   n = last;	int k = 0;		while (i <= m && j <= n)	{		if (a[i] <= a[j])			temp[k++] = a[i++];		else			temp[k++] = a[j++];	}		while (i <= m)		temp[k++] = a[i++];		while (j <= n)		temp[k++] = a[j++];		for (i = 0; i < k; i++)		a[first + i] = temp[i];}void mergesort(int a[], int first, int last, int temp[]){	if (first < last)	{		int mid = (first + last) / 2;		mergesort(a, first, mid, temp);    //左边有序		mergesort(a, mid + 1, last, temp); //右边有序		mergearray(a, first, mid, last, temp); //再将二个有序数列合并	}}bool MergeSort(int a[], int n){	int *p = new int[n];	if (p == NULL)		return false;	mergesort(a, 0, n - 1, p);	delete[] p;	return true;}

归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

注：有的书上是在mergearray()合并有序数列时分配临时数组，但是过多的new操作会非常费时。因此作了下小小的变化。只在MergeSort()中new一个临时数组。后面的操作都共用这一个临时数组。

将上面的mergesort改用泛型编程：

//将有二个有序数列a[first...mid]和a[mid...last]合并。template 
    
     void mergearray(T a[], int first, int mid, int last, T temp[]){	int i = first, j = mid + 1;	int m = mid,   n = last;	int k = 0;	while (i <= m && j <= n)	{		if (a[i] <= a[j])			temp[k++] = a[i++];		else			temp[k++] = a[j++];	}	while (i <= m)		temp[k++] = a[i++];	while (j <= n)		temp[k++] = a[j++];	for (i = 0; i < k; i++)		a[first + i] = temp[i];}template 
     
      void mergesort(T a[], int first, int last, T temp[]){	if (first < last)	{		int mid = (first + last) / 2;		mergesort(a, first, mid, temp);    //左边有序		mergesort(a, mid + 1, last, temp); //右边有序		mergearray(a, first, mid, last, temp); //再将二个有序数列合并	}}template 
      
       bool mergesort(T a[], int n){	T *p = new T[n];	if (p == NULL)		return false;	mergesort(a, 0, n - 1, p);	delete[] p;	return true;}
      
     
    

测试一下：

int main(){    int arr[]={5,4,3,2,1,6,7,8,10,20,2,1};    float arr1[]={1.2, 2.3, 3.5, 5.8, 0.2};    int len=sizeof(arr1)/sizeof(float);    mergesort(arr1,len);    for(int i=0;i
    
     <
     
      <<" ";    }    return 0;}
     
    

参考来源：http://blog.csdn.net/morewindows/article/details/6678165