归并排序(Merge Sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
归并操作(Merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序,也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。
算法思路:
1、把 n 个记录看成 n 个长度为 l 的有序子表
2、进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表
3、重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。
实例分析
以数组 array = [6, 5, 3, 1, 8, 7, 2, 4] 为例,首先将数组分为长度为 2 的子数组,并使每个子数组有序:
1 | [6, 5] [3, 1] [8, 7] [2, 4] |
然后再两两合并:
1 | [6, 5, 3, 1] [8, 7, 2, 4] |
最后将两个子数组合并:
1 | [6, 5, 3, 1, 8, 7, 2, 4] |
排序过程动画演示如下:
