主要思想
该算法是采用分治法，把数组不断分割，直至成为单个元素，然后比较再合并（合并的过程就是两部分分别从头开始比较，取出最小或最大元素的放到新的区域内，继续取两部分中最大或最小的元素，直到这两部分合并完，最后所有的都合并完，最后形成完整的有序序列）
图片理解
## 代码实现
//二路归并排序
/*
二路归并拍序利用了分治的思想
*/
void mergeSort(int left , int right){
if((right - left) <= 0){ //递归结束条件，当待排序列只有一个数据时
return;
}else {
mergeSort(left , (right + left) / 2); //左部分继续划分
mergeSort((right + left) / 2 + 1, right);//右部分继续划分
merge(left , right); //两部分排序
}
}
//传入的待排序列为左边部分有序，有部分有序，但整个待排序列无序如： 1 5 9 10 0 3 4 11
// ---------- -------------
// 左边部分 右边部分
//left是待排序序列第一个数据在数组中的下标
//rigth是待排序序列的最后一个数据在数组中的下标
void merge(int left , int right){
int midleft = (left + right)/2; //划分后左边块的最后一个数据的数组下标
int midright = midleft + 1; //划分后右边块的第一个数据的数组下标
int *arrA = new int [right - left + 1];//动态分配数组，用于存放待排序列的排序结果，长度等于待排序列
int i = left , j = midright;
int k = 0; //表示动态数组下标
while(i <= midleft && j <= right){ //完成在待排序列左右部分中找出最小数并放入动态申请数组中，直到所有待排数据都在动态数组中
if(arr[i] < arr[j]){
arrA[k++] = arr[i++];
}else if(arr[i] >= arr[j]){
arrA[k++] = arr[j++];
}
}
if(i <= midleft){ //因为待排数组左右部分长度可能不相等，故会有一个部分先取完数据，完成待排序列的剩余数据
while(i <= midleft){
arrA[k++] = arr[i++];
}
}else if(j <= right){
arrA[k++] = arr[j++];
}
for(int i = left , k = 0; i <= right;i++,k++){ //把动态申请数组中的有序数据归并到待排数组中
arr[i] = arrA[k];
}
}
void Show(){
for(int i = 0;i<=6;i++){
cout<<arr[i]<<" ";
}
}
int main(){
mergeSort(0,7);
Show();
return 0;
}
结果：