概念
“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。假设待排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为一，然后两两归并，得到【n/2】个长度为2或1的有序表；继续两两归并。。。如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2路归并排序。
归并排序是使用到了分治方法（Divide and Conquer）。
- Divide：将原问题分解为若干子问题，其中这些子问题的规模小于原问题的规模。
- Conquer：递归地求解子问题，当子问题规模足够小时直接求解。
- Merge：将子问题的解合并得到原问题的解。
算法实现
代码语言：javascript复制/*****************归并排序*****************/
int guibing = 10;//和总体表的大小一致
ElemType* B = (ElemType*)malloc((guibing 1) * sizeof(ElemType));//辅助数组B
void Merge(ElemType A[],int low,int mid,int high)
{
int i, j,k;
//表A[low...mid]和A[mid 1...high]各自有序，将他们合并成一个有序表
for (int k = low; k <= mid; k )
B[k] = A[k];
for (int i = low, j = mid 1, k = i; i <= mid && j <= high; k )
{
if (B[i] <= B[j])
A[k] = B[i ];//将较小值复制到A中
else
A[k] = B[j ];
}
while (i <= mid)
A[k ] = B[i ];//若第一个表未检测完，复制
while (j <= high)
A[k ] = B[j ];
}
void Merge_Sort(ElemType A[],int low,int high)
{
if (low < high)
{
int mid = (low high)/2; //划分成两个子序列
Merge_Sort(A,low,mid);
Merge_Sort(A,mid 1,high);
Merge(A,low,mid,high); //归并
}
}
