【算法】归并排序算法的讲解和代码实践

思路

有数组[2, 1, -3, -15, 25, 16, 0, 8]如下：

现对该数组进行排序，使用归并排序算法。
先来讲解一下归并排序的思路，大概分为如下几个步骤：

1. 先将原数组先进行拆分，拆分成若干个足够小的子数组；
2. 将子数组进行排序；
3. 将子数组一一进行归并，直到所有子数组被归并。

讲解

OK，思路了解了，下面就用图示来演示一下各个步骤是怎么做的。

1. 先将原数组先进行拆分，拆分成若干个足够小的子数组：

我们先把上面的数组进行第一次拆分：

拆分成了两部分，分别为[2, 1, -3, -15]和[25, 16, 0, 8]
这样的拆分不够小，我们继续进行拆分：

这样就又把两个子数组分别拆分成了更小的两个子数组[2, 1]、[-3, -15]、[25, 16]、[0, 8]。
好了，这样的拆分足够小了，进行下一步。

2. 将子数组进行排序&