归并排序遵照分治法：
（1）分解divide：将原问题分解成一系列子问题
（2）解决conquer：递归的解决子问题
（3）合并combine：酱紫问题结果合并成原问题的解。
对归并排序如下而已：
分解：将n个元素分成n/2个元素的子序列
解决：用归并排序法对各个子序列递归的排序
合并：合并两个已经排序的子序列。
在对子序列排序时，长度为1标识结束。
废话少说，上代码。
merge_sort.h
/************************************************************************//* 归并排序的思想就是将一个数组分为两个子数组，分别将子数组归并排序，再将将连个已经有序的数组合并一起 也就是一个递归的过程 *//************************************************************************///首先是将两个有序数组合并void Merge(int a[], int start, int middle, int end);void Merge_sort(int a[], int start, int end);
merge_sort.cpp
#include "merge_sort.h"#include#include void Merge(int a[], int start, int middle, int end){ int length_left = middle - start ; //左数组的下标为start...middle-1 int length_right = end -middle; //右面数组下标middle....end -1 int * p_left = (int*)malloc( (length_left + 1) * sizeof(int)); //需设置哨兵故长度加1 int * p_right = (int*)malloc((length_right + 1) * sizeof(int)); for (int i = 0; i < length_left; i++ ) //将左面数组的值复制到新的子数组 { p_left[i] = a[start + i]; } for (int i = 0; i < length_right; i++ ) //将右面数组的值复制到新的子数组 { p_right[i] = a[middle + i]; } p_left[length_left] = INT_MAX; //设置哨兵，标识最后一个元素,子数组结束 p_right[length_right] = INT_MAX; int l = 0; int r = 0; while(start < end){ a[start++] = p_left[l] < p_right[r] ? p_left[l++] : p_right[r++]; //将左，右数组中较小的放到待排序数组中 } free(p_left); free(p_right);}void Merge_sort(int a[], int start, int end){ if (start < end - 1) //是否是最小颗粒也就是说只有一个元素了.也就是说end - start +1 > 2 { int middle = (end + start) / 2; Merge_sort(a,start,middle); Merge_sort(a,middle,end); Merge(a,start,middle,end); }}