合并排序依赖于合并操作，即将两个已经排序的序列合并成一个序列，具体的过程如下：
1申请空间，使其大小为两个已经排序序列之和，然后将待排序数组复制到该数组中。
2设定两个指针，最初位置分别为两个已经排序序列的起始位置
3 比较复制数组中两个指针所指向的元素，选择相对小的元素放入到原始待排序数组中，并移动指针到下一位置
4重复步骤3直到某一指针达到序列尾
5 将另一序列剩下的所有元素直接复制到原始数组末尾
代码参考
https://blog.csdn.net/fly_yr/article/details/8550097?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%90%88%E5%B9%B6%E6%8E%92%E5%BA%8F&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-1-8550097.142v99pc_search_result_base5&spm=1018.2226.3001.4187
#include <iostream>
#include <stdlib.h>
#include <time.h>
#define N 15
using namespace std;
void Merge(int * array,int low,int middle,int high);
void MergeSort(int * array,int low,int high);
int main()
{
int array[N];
srand(time(0));//设置随机化种子，避免每次产生相同的随机数
for(int i=0 ; i<N ; i++)
{
array[i] = rand()%101;//数组赋值使用随机函数产生1-100之间的随机数
}
cout<<"排序前："<<endl;
for(int j=0;j<N;j++)
{
cout<<array[j]<<" ";
}
cout<<endl<<"排序后："<<endl;
//调用合并排序函数对该数组进行排序
MergeSort(array,0,N-1);
for(int k=0;k<N;k++)
{
cout<<array[k]<<" ";
}
cout<<endl;
return 0;
}//main
void MergeSort(int *array,int low,int high)
{
if(low<high)
{
int middle = (low+high)/2;
MergeSort(array,low,middle);
MergeSort(array,middle+1,high);//注意取值middle+1 至 q
Merge(array,low,middle,high);
}//if
}//MergeSort
void Merge(int *array,int low,int middle,int high)
{
int lSize = middle-low+1;//low至middle之间的数据个数
int rSize = high-middle;//middle至high之间的数据个数
int *lArray = new int[lSize];//声明左半边数组
int *rArray = new int[rSize];//声明右半边数组
for(int i=0;i<lSize;i++)
{
lArray[i] = array[low+i];//为左半边数组赋值
}//for
for(int j=0;j<rSize;j++)
{
rArray[j] = array[middle+j+1];//为右半边数组赋值
}//for
/*a为了Array数组的循环变量，b为rArray数组的循环变量，
*k为原数组array的循环变量
*/
int a=0,b=0,k;
for(k=low;k<=high;k++)
{
if(a>=lSize)
{
array[k] = rArray[b++];
}else if(b>=rSize){
array[k] = lArray[a++];
}else{
if(lArray[a]<=rArray[b])
{
array[k] = lArray[a++];
}else{
array[k] = rArray[b++];
}//else
}//else
}//for
}//Merge
