归并排序
刷leetcode的题目的时候有一个部分涉及到了两个有序数组的合并，其实仔细想想算法并不复杂，属于归并排序中的一次归并，那么下面做一个简单的笔记。
归并
首先，归并排序中有分而治之的思想，也就是将一个无序的数组的有序部分，不断的归并成更大的有序的部分，直至整个数组达到有序的状态。
我们一开始提到了，归并这个操作，实际上是对两个或者多个有序数据进行整个再次达到有序状态的算法。这个算法比较简单，我们下面举一个例子。
A: 2,3,4,8,9
B: 3,4,5,7,8
我们有A,B两个数组，每一个数组都是有序的，那么我们要将他们归并成另一个有序的数组，该如何做呢？
一般的最直接的做法就是，首先我们分配一个新的数组，长度等于AB两个数组的长度之和，那么在这里我们需要分配一个长度为10的数组。我们设定两个指针，分别指向A数组和B数组的第一个元素，在这里我们直接使用索引。
PtrA=0 PtrB=0
下面我们来开始归并。我们依次比较当前A和B指针指向的元素，我们选取两者最小的一个，放入新的数组中。假设两者相等，那么我们依次将A的元素和B的元素放入新的数组中，来保证排序的稳定性。经过第一次的归并之后，数组的内容如下(指针指的下一个元素，前面用.号标识)：
PtrA=1 PtrB=0
A: 2,.3,4,8,9
B: .3,4,5,7,8
C: 2
第二次归并，因为指向的元素等同，于是全部放入新的数组中。进行第二次归并之后，内容如下：
PtrA=2 PtrB=1
A: 2,3,.4,8,9
B: 3,.4,5,7,8
C: 2,3,3
第三次归并也是相同的元素。进行第三次归并之后，内容如下：
PtrA=3 PtrB=2
A: 2,3,4,.8,9
B: 3,4,.5,7,8
C: 2,3,3,4,4
第四次归并，由于指向的是8和5，把较小的5放入新的数组，同时B的索引+1：
PtrA=3 PtrB=3
A: 2,3,4,.8,9
B: 3,4,5,.7,8
C: 2,3,3,4,4,5
第五次归并，将较小的7放入新的数组，同时B的索引+1：
PtrA=4 PtrB=4
A: 2,3,4,.8,9
B: 3,4,5,7,.8
C: 2,3,3,4,4,5,7
第六次归并，元素相等，依次放入新的数组，两者的索引都+1。但是我们看到了，对于B数组，索引已经是最大值了，所以B的元素都归入了新的数组后，我们剩下要做的就是把A数组的元素都并入新的数组：
PtrA=4 PtrB=Done
A: 2,3,4,8,.9
B: 3,4,5,7,8
C: 2,3,3,4,4,5,7,8,8
由于
PtrA=Done PtrB=Done
A: 2,3,4,8,9
B: 3,4,5,7,8
C: 2,3,3,4,4,5,7,8,8,9
整个归并就此完成。
对无序数组的归并排序
我们已经知道，归并只能针对于两个或者多个有序队列的归并，那么对于无序的队列，我们应该怎么做呢？
假设有一个无序队列
7,3,9,1,4,2,8,5
我们依次将它拆开，分为8个数组
[7] [3] [9] [1] [4] [2] [8] [5]
我们可以看到，我们将整个无序的数组，分隔成了8个有序数组，因为每个数组的元素只有1个，那当然是有序的啦。接下来，我们两两进行归并操作：
[3,7] [1,9] [4,2] [5,8]
我们可以看到，进行了一次归并后，元素变成了2个，同时它们依旧是有序状态，我们再一次进行归并：
[1,3,7,9] [2,4,5,8]
在进行一次归并，就归并了整个数组了：
[1,2,3,4,5,7,8,9]
至此操作完成。
作者
