归并排序

归并排序和快速排序一样，也是基于分治法的排序，其平均复杂度O（nlgn），属于稳定排序。

核心思路：把一个待排序的序列划分成两个子序列，然后再把子序列继续划分下去，直到子序列的长度为1或为空跳出递归，然后开始合并，最开始的归并是把两个元素合成一个长度为2的有序序列，然后再往外层跳转，合并成一个长度为4的有序序列。把两个有序的子序列合并成一个序列是关键

@1：先确定子序列的长度

@2：开启辅助空间，存放原始的待排序列

@3和@4：把两个子序列分别复制到辅助空间，这里要考虑边界问题

@5和@6：i记录的是左序列的当前位置，j记录的是右序列的当前位置，k记录的是目标数组的下一个待排序位置。

@7：两个子序列都从左往右移动，每一次比较i和j所指向的位置的元素，小的复制到目标序列中，然后位置更新。i的最大值是n1-1，j的最大值是n2-1

@8：小于等于号是维护稳定性的关键，因为是非递减序列，所以左侧子序列较小，右侧子序列较大，如果两个相等的话，先让左侧子序列的元素复制到目标数组，两个相同的元素的相对位置不会改变

@9和@10：如果i到达n1或是j到达n2，就跳出了@7循环，然后进入@9或@10循环，意味着某个子序列已经全部进入目标数组，另一个子序列可以直接复制过去，这在排两个有序链表的时候，直接把另一个链表的指针复制到目标链表就可以了，这里是数组，还要一个一个的复制。

@11：删除辅助空间

这个不以两个子序列的区间为循环控制条件，而是以整个目标数组的区间[p, r]为循环控制条件。

@1：开辟多余一个空间

@2：存放足够大的值

@3：同样i和j指向子序列的当前待排序元素 位置，而循环控制条件为[p, r]，因为任何一个子序列到达最后一个元素（也就是那个足够大的值位置）后，另外一个都不能大于它。假如左子序列先到达终点，则则判断条件始终会转向@5，进而把右子序列的剩余元素复制到目标数组；假如右子序列先到达终点，则判断条件始终转向@4。