归并原理：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾注：此处指针表示能找到该元素地址 并非 一定是c语言中的指针
实现：
#include<stdio.h>
#include<stdlib.h>
void merge(int a[], int tmp[], int left, int right, int r_end)
{
int l_end;//左边数组终点
int element_num;
int tmp_pos; //临时数组初始位置
tmp_pos = left;
l_end = right-1;//默认两段子序列相邻、
element_num = r_end - left + 1;
while(left <= l_end && right <= r_end){
if(a[left] <= a[right]){
tmp[tmp_pos++] = a[left++];
}
else{
tmp[tmp_pos++] = a[right++];
}
}
while(left <= l_end){
tmp[tmp_pos++] = a[left++];
}
while(right <= r_end){
tmp[tmp_pos++] = a[right++];
}
int i;
for(i = 0; i < element_num; i++, r_end-- ){
a[r_end] = tmp[r_end];
}
}
// a[r_end--] = tmp[r_end--]; 错误 此处 r_end减了两次
// a[--tmp_pos] = tmp[r_end--] 此种用法要注意 最后的tmp_pos指向末尾元素下一位置
void m_sort(int a[], int tmp[], int left, int r_end)
{
int center;
if(left < r_end){
center = (left + r_end)/2;
m_sort(a, tmp, left, center);
m_sort(a, tmp, center+1, r_end);
merge(a, tmp, left, center+1, r_end);
}
}
void merge_sort(int a[], int n)
{
int *tmp = (int *)malloc(sizeof(int)*n);
if(tmp == NULL){
printf("申请内存失败");
return ;
}
m_sort(a, tmp, 0, n-1);
free(tmp);
}
int main()
{
int a[] = {1,3,5,2,4,6,9};
int n = sizeof(a)/sizeof(a[0]);
merge_sort(a, n);
int i;
for(i = 0; i < n; i++ ){
printf("%d\n",a[i]);
}
return 0;
} 
