#MERGE-SORT
* 输入：未排序数组A[p,r]
* 输出：排序数组A[p,r]
#MERGE分析：
* 输入：数组A[p,q,r]，A[p,q]和A[q+1,r] 中的元素都按照从小到大的排列好
* 输出：将两个已经排序的部分合并为一个单一的排序数组A[p,r]
1. A[p,q]和A[q,r]分别复制到临时数组left[左侧元素个数 + 1]，right[右侧元素个数 + 1]之中,
额外添加MAX作为哨兵元素，
2. 比较两个数组的最小值，并把更小的元素放入A中
3. 如果其中一侧显示为MAX，则不可能为最小，此时另一侧元素放入输出堆，
重复步骤2直到两侧都显示为MAX，一旦发生这种情况，表明左右两侧元素除了MAX都被放入到了输出堆，
所以，步骤2重复次数除MAX外的元素总数，即r-p+1
重复r-q+1次
##pseudocode:
```
MERGE(A[p,q,r])
n1 = p-q+1
n2 = r-q
new arrays left[0..n1] and right[0..n2]
left[n1] = right[n2] = MAX
for i = 0 to (n1 - 1)
left[i] = A[p + i]
for j = 0 to (n2 -1)
right[i] = A[q + 1 + j]
i = j = 0
for key = p to r
if left[i] <= right[j]
A[key] = left[i]
i = i + 1
else A[key] = right[j]
j = j + 1
```
#C语言实现
```
void MERGESORT(int a[], int low, int high)
{
if (low < high) {
int middle = (low + high) / 2;
MERGESORT(a, low, middle);
MERGESORT(a, middle + 1, high);
merge(a, low, middle, high);
}
}
void merge(int a[], int low, int middle, int high)
{
// 临时数组left，right，最后一个元素为哨兵元素
int n1 = middle - low + 1;
int n2 = high - middle;
int* left = (int*)malloc((n1 + 1) * sizeof(int));
int* right = (int*)malloc((n2 + 1) * sizeof(int));
if (left && right) {
left[n1] = right[n2] = MAX;
// a[low, middle]复制到left[0, n1 - 1]
for (int i = 0; i < n1; i++)
left[i] = a[low + i];
for (int j = 0; j < n2; j++)
right[j] = a[j + middle + 1];
int i = 0, j = 0;
for (int key = low; key <= high; key++) {
if (left[i] <= right[j]) {
a[key] = left[i];
i++;
}
else {
a[key] = right[j];
j++;
}
}
free(left);
free(right);
}
}
```
