归并排序是建立在归并操作上的一种有效、稳定的排序算法，该算法采用非常经典的分治法（分治法可以通俗的解释为:把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化），归并排序的思路很简单，速度呢，也仅此于快速排序，接下来我们详细的看看归并排序的过程。
基本思路：
第一步：将序列中待排序数字分为若干组，每个数字分为一组。
第二步：将若干组两两合并，保证合并的组都是有序的。
第三步：重复第二步的操作，直到剩下最后一组即为有序数列。
详细步骤：
首先将数组中待排序数字分成若干组,每个数字为一组
相邻的两组进行对比，并且两两合并，保证合并后都是有序的数列，i（数字8）> j（数字4）需要交换位置（最终呈现一个升序的数组），经过比较合并后两个数存入一个空的指针里
其他组按照此方法依次合并，从8个组合并成4个组
继续相邻的两个组进行合并
定义两个变量i,j分别代表P1里的第一个值（4）和P2里的第一个值（5），i和j进行比较，i < j（4 < 5）,将数字4移入p中，i向后移动一位
i和j进行比较，i > j（8 > 5 ）,将数字5移动到p中（4的后一位），j后移一位
i 和j继续进行比较，i > j （8 > 7）,将数字7移动到p中（5的后一位），p2中没有待排序的数字，所以比较结束，p1中剩下的数字移动到p中（7的后一位），合并结束。旁边两个序列按照同样的方式进行合并，最后得到两个有序序列，将这两个有序序列通过上面的方式继续进行合并
i和j进行比较，i > j（4 > 1）,i不动，p2中的数字1移动到p中，j向后移动一位
i继续和j比较，i > j（4 > 2）,数字2移动到p中（1的后一位），j向后移动一位
i继续和j比较，i > j（4 > 3）,数字3移动到p中（2的后一位），j向后移动一位
i继续和j比较，i < j（4 <6）,数字4移动到p中（3的后一位），i向后移动一位
i继续和j比较，i < j（5 < 6）,数字5移动到p中（4的后一位），i向后移动一位
i继续和j比较，i > j（7 >6）,数字6移动到p中（5的后一位），p2中已经没有待排序的数字，所以比较结束，p1中剩下的数字移动到p中（6的后面）
最后得到一个有序的数列 ，归并排序结束
源代码 如下：
#include <stdio.h>
#include <stdlib.h>
void G_qsort(int *a,int first,int mid,int last,int *temp)
{
int n = mid,m = last;
int k = 0;
int i = first,j = mid+1;
while(i <= n && j <= m) // 两边同时进行
{
if(a[i] <= a[j]) // i和j进行比较
{
temp[k++] = a[i++]; // 如果i <= j,则i的值移动到temp里面
}
else
{
temp[k++] = a[j++]; // 如果i > j,则j的值移动到temp里面
}
}
while(i <= n)
{
temp[k++] = a[i++];
}
while(j <= m)
{
temp[k++] = a[j++];
}
for(i = 0; i < k; i++)
{
a[first+i] = temp[i];
}
}
void G_sort(int *a,int first,int last,int *temp)
{
if(first < last) // 当同时到达一个数时结束判断
{
int mid = (first+last)/2; // 找到中间值
G_sort(a,first,mid,temp); // 递归函数左边
G_sort(a,mid+1,last,temp); // 右边
G_qsort(a,first,mid,last,temp); // 进行排序
}
}
int sort(int *a,int n)
{
int *p = malloc(n); // 分配内存大小
if(p == NULL)
{
return -1;
}
else
{
free(p);
G_sort(a,0,n-1,p); // 调用函数传参，0和n-1为第一个数和最后一个数下标
p = NULL;
return 1;
}
}
int main()
{
int a[8]={8,4,5,7,1,3,6,2};
int i;
sort(a,8); // 调用函数传参
for(i = 0; i < 8; i++)
{
printf("%d",a[i]);
}
printf("\n");
return 0;
}
文章来源：学到牛牛 IT培训
