归并排序，众所周知，其核心是把2个有序的数组，合并成1个大的有序数组。重复这个过程，直到整个数组有序。
但这个算法有几个可以优化的地方：
- 对小规模的数组使用插入排序。插入排序对于小数组非常高效，因此我们不需要归并2个有序的小数组，直接对它们进行插入排序即可。
- 测试数组是否已经有序。如果前一个有序数组的最后一个元素小于后一个有序数组的第一个元素，那么整个数组已经有序，无需归并。
- 逐次交换输入数组和辅助数组的角色。第一次循环，我们将输入数组中的元素归并到辅助数组中(但并不复制回输入数组)；第二轮循环，我们将辅助数组中的元素归并>到输入数组中。依此类推。如果最后一个归并的目的地是辅助数组，就将其复制回输入数组；如果是输入数组，则什么也不用做。
- 将要归并的两个数组中的第二个倒置(或倒序复制到辅助数组中)，这样就不需要判断一个其中一个数组的元素是否已经用完。但在使用优化3的情况下，我们不需要多复 制一遍元素，特意倒置数组显得好处有限。
这次我们来实现优化2和3.