# 认识“分治”思想

本节我们要学习的两个排序算法都是对“分治”思想的应用。 “分治”，分而治之。其思想就是将一个大问题分解为若干个子问题，针对子问题分别求解后，再将子问题的解整合为大问题的解。

利用分治思想解决问题，我们一般分三步走：

• 分解子问题
• 求解每个子问题
• 合并子问题的解，得出大问题的解

下面我们一起来看看分治思想是如何帮助我们提升排序算法效率的。

# 归并排序

# 思路分析

归并排序是对分治思想的典型应用，它按照如下的思路对分治思想“三步走”的框架进行了填充：

• 分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
• 求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。 合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组

# 真实排序过程演示

下面我们基于归并排序的思路，尝试对以下数组进行排序：

[8, 7, 6, 5, 4, 3, 2, 1]

• 首先重复地分割数组，整个分割过程如下：
• 首次分割，将数组整个对半分：

[8, 7, 6, 5,| 4, 3, 2, 1]

二次分割，将分割出的左右两个子数组各自对半分：

[8, 7,| 6, 5,| 4, 3,| 2, 1]

三次分割，四个子数组各自对半分后，每个子数组内都只有一个元素了：

[8,| 7,| 6,| 5,| 4,| 3,| 2,| 1]

接下来开始尝试解决每个子问题。将规模为1的子数组两两合并为规模为2的子数组，合并时确保有序，我们会得到这样的结果：

[7, 8,| 5, 6,| 3, 4,| 1, 2]

继续将规模为2的按照有序原则合并为规模为4的子数组：

[5, 6, 7, 8,| 1, 2, 3, 4]