不得不说的分而治之归并排序算法

排序算法的第四章——归并排序。归并排序涉及到了「分治」，其中的合并操作，更是一种非常常见的处理方法。同时使用场景也不再单单是使用在排序中，还可以用于...

这是我们学习的第四个排序算法，归并排序算法。经过我们前面的学习我们已经学习了：

它们的时间复杂度都为O(N2)O(N^2)O(N2),空间复杂度为O(1)O(1)O(1)。算法性能上并没有孰强孰弱，不过在「稳定性」上存在差别。

• 冒泡、插入排序能保证「稳定性」
• 插入排序不能保证「稳定性」

相信有的同学有疑问：前面学习的这3个排序的时间复杂度都指数级别的，有没有更快的排序算法呢？？

答案是：肯定有的。

今天我们就来学习比前面排序更快的算法：归并排序。

算法描述

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。—— 百度百科

根据上述描述我们可以得到两个关键字：

分治

在算法中，分治是一种解决问题的通用策略，它的基本思想是将一个大问题分解成若干个相同或相似的子问题，然后分别解决这些子问题，最后将子问题的解合并起来，得到原问题的解。分而治之

分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。

分治策略通常包含三个步骤：

分治策略在解决许多问题时都非常有效，特别是那些可以被分解成相似子问题的问题。一些经典的算法和问题，如归并排序、快速排序、汉诺塔问题、最大子数组问题等都可以通过分治策略来解决。

归并

归并其实就是将子问题的解合并起来，分治里面包含了归并这一步骤。那么我为什么要单独把他拎出来呢？这是因为在很多题目里面并没有涉及到「分治」而是这又单纯的「归并」或者「合并」操作，所以我们还是要掌握和理解这个归并的操作的。

归并排序是「分治」的应用，将待排数组递归或者迭代地分为左右两半，直到数组长度为1，然后合并左右两个数组，在合并中进行排序操作。

稳定性

归并排序的稳定性在于合并时，两个相等的元素我们可以判断，当左右两个数组前的元素相等时，左边的元素总会被放在左侧来保证其是稳定的。类似If(left[i]r时出现越界。
//l=r时数组长度为1。直接返回
if(l>=r) return;
//求出当前数组的中间下标。l+(r-l)/2防止值溢出
int mid = l+(r-l)/2;
//定义指标，i、j。
//i为左数组的第一个下标。j为右数组的第一个下标。
int i = l,j = mid+1;
//临时数组第一个下标
int k = 0;
//递归
sort(q,i,mid);
sort(q,j,r);