归并排序是一种分治思想的应用，所以也适合处理大数量的排序，因此也是一种外排序算法，磁盘排序算法，应用场景也较多，比如mysql的排序，sharding-jdbc的排序，
- 下面文字是shardding-jdbc官网的一段描述，官网地址如下，友情提示:官网左边导航栏最下方支持中英文语言切换哦
https://shardingsphere.apache.org/document/current/cn/features/sharding/principle/merge/排序归并，由于在SQL中存在ORDER BY语句，因此每个数据结果集自身是有序的，因此只需要将数据结果集当前游标指向的数据值进行排序即可。这相当于对多个有序的数组进行排序，归并排序是最适合此场景的排序算法。
该算法是将已有的子序列不断进行合并从而最终达到全局有序，一般我们的实现都是二路归并，就是两个有序的子序列进行合并，但也可以进行多路归并(将大于两个的子序列进行合并)
我们通过一个简单的归并排序(递归)来分析时间，空间复杂度
我们分析上面的代码，看看归并排序的复杂度怎么样呢，首先递归的终止条件必须确定，就是数组大小小于等于1时，递归终止，我们不断通过对待排序的数据array进行折中，从而达到最终二路归并时left，right的数组大小都是1，我们看下图，方便大家理解递归和归并，由图得知，我们每次对数组拆分都是一分为二的才做，比如数组长度为4，拆分到最后为1时就是4/2/2的操作，所以递归拆分的时间复杂度是logN(以2为底)，在归并时是对两个有序的序列开始做合并，递归了n次，所以要合并n次，但每次合并时遍历子序列，假设子序列长度为n，所以整体时间复杂度为nlogN,每次合并时申请新的空间存储合并后的有序数组返回，所以空间复杂度为O(n),
利用数求递归的复杂度，这是一种简单思想，现在，我们需要知道这棵树的高度 h，用高度 h 乘以每一层的时间消耗 n，就可以得到总的时间复杂度n * h，而满二叉树的高度是log2(n),所以时间复杂度一目了然。
复杂度总结
时间复杂度：nlog2(n) 空间复杂度：O(n)
除了递归实现，你能想到非递归怎么实现吗？
非递归实现二路归并排序
一般非递归代替递归，递归其实利用了操作系统的栈空间存储临时数据，所以两种方案，一是利用栈数据结构，二是利用变量(这种相对局限一点)
分析一下上面的代码的时间复杂度还是nlog2(n)吗？答案是是的，自己分析一下哦
磁盘文件归并排序(也就是经常说的1亿数据,10M内存,请排序）
核心思路（多路排序）
- 每次读取一定量的数据(10M内存能放下)，排序后单独写入小文件,直到大文件全部排完序写入很多（不再是两个，所以多路排序）个小文件，这时所有小文件中的数据是有序的
- 所有小文件中的数据每次读取一个做归并排序写入最终的结果文件中，直到所有小文件都处理完成
不多说，贴代码，看代码说事
