分治算法

分治（divide and conquer），全称分而治之，是一种非常重要且常见的算法策略。分治通常基于递归实现，包括“分”和“治”两个步骤。

1. 分（划分阶段） ：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
2. 治（合并阶段） ：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解。

“归并排序”是分治策略的典型应用之一。

分（divide）：把数组一分为二，直到子问题只剩一个元素
                        [4, 1, 3, 2]
                       /            \
                [4, 1]                [3, 2]
                /    \                /    \
             [4]     [1]           [3]     [2]

治（conquer）：单个元素本身就是已排序的解

合并（merge）：自底向上把相邻子序列归并
             [4] + [1]      ->  [1, 4]
             [3] + [2]      ->  [2, 3]
             [1, 4] + [2, 3] ->  [1, 2, 3, 4]

每一层的合并代价与当前区间的总元素数成正比，共 (\log_2 n) 层，因此总时间复杂度是 (O(n \log n))。

分治算法通过把一个问题分解成多个，这样在非常数级算法时，复杂度可能会显著降低，除非要排序的项目特别少。

‍