什么是归并排序？

概念

“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。假设待排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为一，然后两两归并，得到【n/2】个长度为2或1的有序表；继续两两归并。。。如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2路归并排序。

归并排序是使用到了分治方法（Divide and Conquer）。

1. Divide：将原问题分解为若干子问题，其中这些子问题的规模小于原问题的规模。
2. Conquer：递归地求解子问题，当子问题规模足够小时直接求解。
3. Merge：将子问题的解合并得到原问题的解。

算法实现

/*****************归并排序*****************/
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