一、算法原理
归并排序是一种常用的排序算法，属于稳定排序法，其时间复杂度为
归并排序就是将两个已经分别排好序的数组A和B合并为一个排好序的数组C。
如果数组散乱的数组，则需要将数组元素分别按照长度为d=2^n，n=0,1,2,3,…，进行分组，然后 对相邻的两组进行升序或者降序进行重新排序。具体过程就是首先取长度d=1，即将数组的每个元素作为一个子数组，然后把相邻的两个子数组作为一对进行归并排序，直到整个数组均排序完成。之后进行长度d=2，即把相邻的两个元素作为一个子数组，再对两个相邻的子数组进行归并排序，直到整个数组排序完成。之后再分别进行d=4，8,…的归并排序，直到整个数组已经是排好序的数组结束。
归并排序算法原理是固定的，但是具体实现的时候，方法有很多，本文给出了其中的一种方法。
以下Demo演示归并排序的过程。
**Demo：**假设有数据如下表所示：
第一趟归并排序： 每个元素为一个数组，总共有7个，相邻的两个数组依次进行排序，过程如下：
第二趟归并排序： 相邻的2个元素组成一个数组，不足的部分也自成一个数组，总共有4个，相邻的两个数组依次进行排序，过程如下：
第三趟归并排序： 相邻的4个元素组成一个数组，不足的部分也自成一个数组，总共有2个，相邻的两个数组依次进行排序，过程如下：
至此，归并排序结束。
由上述归并排序过程可以看出，数组中的元素在每一趟归并排序中，不一定能刚好分成偶数个数组，可能会存在“尾巴”数据。在编制算法的时候，就需要单独考虑这些“尾巴”的排序问题。当剩余的“尾巴”元素个数小于等于d的长度时，对这些数据不需要处理，如上述Demo的第一趟归并排序，剩余尾巴元素2。当剩余的“尾巴”元素个数大于d的长度小于2d长度时，需要分成2组进行归并排序，如上述Demo的第二趟排序中，剩余的尾巴元素4,7和2，则4,7组成一个数组，2组成一个数组，然后进行归并排序。
从上述Demo可以看出，归并排序的原理非常简单。只是在处理“尾巴”元素时，需要单独考虑而已。
二、归并排序算法之C++程序
1.两个子数组归并排序算法
//对数组a（长度为m）和数组b（长度为n）进行非递增排序（一趟归并排序），存储到数组c void Merge( int a[], int m, int b[], int n, int c[] ){int i, j, k;i = j = k = 0;while( i < m && j < n ){if( a[i] < b[j] ){c[k++] = a[i++];}else{c[k++] = b[j++];}}while( i < m ){c[k++] = a[i++];}while( j < n ){c[k++] = b[j++];}}
2.归并排序
//对长度为len的数组arr使用多趟归并排序算法进行排序 void MergeSort( int arr[], int len ){int i, j, k, n, m, x, xx;unsigned int d; x = int ( log(len) / log(2) );//printf( "指数x=%d\n", x );int *a, *b, *c;//处理排序的趟数 if( int( pow( 2, x ) ) == len ){xx = x - 1;}else{xx = x;}//根据事先计算的趟数进行归并排序 for( int t = 0; t <= xx; t++ ){d = 1 << t;//向左移位，d的值分别是1,2,4,8，... a = new int[d];b = new int[d];c = new int[2*d];int newLen = int( len / ( 2*d ) ) * 2 * d; //对长度是2d的偶数倍长度内的数据使用多趟归并排序 for( k = 0; k < newLen; k += 2*d ){i = 0;//依次从数组arr中截取长度为d的元素存放到a和b for( j = k; j < k+d; j++ ){a[i] = arr[j];b[i++] = arr[j+d];}Merge( a, d, b, d, c );//一趟归并排序//把排序结果c存到原始数组arr中 i = 0;for( j = k; j < k+2*d; j++ ){arr[j] = c[i++];}}//处理有尾巴的情形 int tail = len % (2*d);if( tail != 0 ){m = n = 0;//if( tail > d && tail < ( 2 * d ) )if( tail > d ){a = new int[d];m = d;b = new int[tail-d];n = tail-d;i = 0;for( j = newLen; j < newLen + d; j++ ){a[i++] = arr[j]; }i = 0;for( j = newLen + d; j < len; j++ ){b[i++] = arr[j]; }c = new int[ m+n ];Merge( a, m, b, n, c );i = 0;for( j = newLen; j < len; j++ ){arr[j] = c[i++];}}}//为方便观察排序结果，向屏幕输出每趟排序结果printf( " No. %d time sort: ", t+1 );for( n = 0; n < len; n++ ){printf( "%5d", arr[n] ); }printf( "\n" );}delete[] a, b, c;}
3.完整的代码
#include "stdio.h" #include"math.h"void MergeSort( int arr[], int len );void Merge( int a[], int m, int b[], int n, int c[] );int main(){int i;int arr[] = {3, 10, 9, 6, 7, 1, 8, 2, 4, 5 };int len = 10;printf( " Initial Array: " );for( i = 0; i < len; i++ ){printf( "%5d", arr[i] );}printf( "\n" );MergeSort( arr, len );return 0;}//对数组a和数组b进行非递增排序（一趟归并排序），存储到数组c void Merge( int a[], int m, int b[], int n, int c[] ){int i, j, k;i = j = k = 0;while( i < m && j < n ){if( a[i] < b[j] ){c[k++] = a[i++];}else{c[k++] = b[j++];}}while( i < m ){c[k++] = a[i++];}while( j < n ){c[k++] = b[j++];}}//对长度为len的数组arr使用归并排序算法进行排序 void MergeSort( int arr[], int len ){int i, j, k, n, m, x, xx;unsigned int d; x = int ( log(len) / log(2) );int *a, *b, *c;//处理排序的趟数 if( int( pow( 2, x ) ) == len ){xx = x - 1;}else{xx = x;}//根据事先计算的趟数进行归并排序 for( int t = 0; t <= xx; t++ ){d = 1 << t;//向左移位，d的值分别是1,2,4,8，... a = new int[d];b = new int[d];c = new int[2*d];int newLen = int( len / ( 2*d ) ) * 2 * d; //对长度是2d的偶数倍长度内的数据使用多趟归并排序 for( k = 0; k < newLen; k += 2*d ){i = 0;//依次从数组arr中截取长度为d的元素存放到a和b for( j = k; j < k+d; j++ ){a[i] = arr[j];b[i++] = arr[j+d];}Merge( a, d, b, d, c );//一趟归并排序//把排序结果c存到原始数组arr中 i = 0;for( j = k; j < k+2*d; j++ ){arr[j] = c[i++];}}//处理有尾巴的情形 int tail = len % (2*d);if( tail != 0 ){m = n = 0;if( tail > d ){a = new int[d];m = d;b = new int[tail-d];n = tail-d;i = 0;for( j = newLen; j < newLen + d; j++ ){a[i++] = arr[j]; }i = 0;for( j = newLen + d; j < len; j++ ){b[i++] = arr[j]; }c = new int[ m+n ];Merge( a, m, b, n, c );i = 0;for( j = newLen; j < len; j++ ){arr[j] = c[i++];}}}//为方便观察排序结果，向屏幕输出每趟排序结果printf( " No. %d time sort: ", t+1 );for( n = 0; n < len; n++ ){printf( "%5d", arr[n] ); }printf( "\n" );}delete[] a, b, c;}
4.测试用例
测试用例一
测试用例二
测试用例三
测试用例四
