归并排序原理：将一个数组分成由左右两个数组，如果左右两个数组为有序数组，则合并成为一个有序数组，排序完成

过程：

• 将数组分成左右两个数组（此时左右两个数组是无序的，所有需要先对左右两个数组排序）
• 对左右两个数组分别排序（递归）
• 合并左右两个有序数组

实现：

#include <stdio.h>
#include <stdlib.h>

/**
* 合并2个有序序列
*/
void mergeData(int *data,int start,int mid,int end)
{
 int *r;

 if((r = (int *)malloc(sizeof(int) * (end - start + 1))) == NULL)
 {
     return;
 }

 int k = 0,leftStart = start,leftEnd = mid,rightStart = mid + 1,rightEnd = end;

 while(leftStart <= leftEnd && rightStart <= rightEnd)
 {//有一个序列结束了则结束比较

     if(*(data + leftStart) < *(data + rightStart))
     {
         *(r + k) = *(data + leftStart);
         leftStart ++;
     }
     else
     {
         *(r + k) = *(data + rightStart);
         rightStart ++;
     }

     k ++;
 }

 //将剩余的数据追加到r末尾
 while(leftStart <= leftEnd)
 {
     *(r + k) = *(data + leftStart);
     leftStart ++;
     k ++;
 }

 while(rightStart <= rightEnd)
 {
     *(r + k) = *(data + rightStart);
     rightStart ++;
     k ++;
 }

 //将合并后的数组依次存储到原数组
 int i,j;
 for(i = 0,j=start;i < k;i++,j++)
 {
     *(data + j) = *(r + i);
 }
}
/**
* 归并排序
*/
void mergeSort(int *data,int start,int end)
{
 if(start >= end)
 {
     return;
 }

 //将数组分成2部分,分别排序，在合并
 int mid = (end + start)/2;//分成2个数组
 mergeSort(data,start,mid);//对左边排序
 mergeSort(data,mid + 1,end);//对右边排序
 mergeData(data,start,mid,end);//合并
}
void myPrint(int *data,int size)
{
 int index;
 for(index = 0;index < size;index ++)
 {
     printf("%d,",*(data + index));
 }
}
int main()
{
 int a[] = {23,12,1,90,21,80};
 mergeSort(a,0,sizeof(a)/sizeof(int) - 1);
 myPrint(a,sizeof(a)/sizeof(int));
 return 1;
}