一 算法设计

合并排序是采用分治策略进行排序的算法，是分治算法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略。

算法步骤如下。

1 分解

将待排序元素分成大小大致相同的两个子序列。

2 治理

对两个子序列进行合并排序。

3 合并

将排好序的有序子序列进行合并，得到最终的有序序列。

二 算法图解

首先将待排序的元素分成大小大致相同的两个子序列，然后把子序列分成大小大致相同的两个子序列，如此下去，直到分解成一个元素为止，这时含有一个元素的子序列就是有序的；然后执行合并操作，将有两个有序的子序列合并为一个有序的序列，如此下去，直到所有元素都合并为一个有序序列时为止。

三 算法详解

1 合并操作

为了进行合并，需要一个合并函数 merge(A,low,mid,high)，该函数将排好序的两个子序列A[low,mid]和A[mid+1,high]进行合并。其中，low、high 代表待合并的两个子序列在数组中的下界和上界，mid 代表下界和上界的中间位置，如下图所示。

这里有3个工作指针 i、j、k 和一个辅助数组B。其中 i 和 j 分别指向两个待排序的子序列中当前待比较的元素，k 指向辅助数组 B 中待放置元素的位置。比较 A[i] 和 A[j] ，将较小的赋值给B[k]，相应的指针同时向后移动。如此反复，直到所有元素都处理完毕。最后把辅助数组 B 中排好序的元素复制到数组 A 中，如下图所示。

第1次比较时，A[i] = 4, A[j] = 2,将较小的元素 2 放入数组 B 中，j++,k++。

第2次比较时，A[i] = 4, A[j] = 6,将较小的元素 4 放入数组 B 中，i++,k++。

第3次比较时，A[i] = 9, A[j] = 6,将较小的元素 6 放入数组 B 中，j++,k++。

第4次比较时，A[i] = 9, A[j] = 18,将较小的元素 9 放入数组 B 中，i++,k++。

第5次比较时，A[i] = 15, A[j] = 18,将较小的元素 15 放入数组 B 中，i++,k++。

第6次比较时，A[i] = 24, A[j] = 18,将较小的元素 18 放入数组 B 中，j++,k++。

第7次比较时，A[i] = 24, A[j] = 20,将较小的元素 20 放入数组 B 中，j++,k++。

此时，j > high 的后半部分处理完毕，但前半部分还剩余元素，该怎么办？将剩余元素照搬到数组 B 就可以了。

完成合并后，需要把辅助数组 B 中的元素复制到原来数组 A 中。

2 合并排序

将序列分为两个子序列，然后对子序列进行递归排序，再把两个已排好序的子序列合并成一个有序序列。

四 算法实现

归并排序实战_实践求真知-CSDN博客

https://blog.csdn.net/chengqiuming/article/details/114706150