给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例:
输入: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
示例代码1（直接合并后再排序）：
class Solution(object):
def merge(self, A, m, B, n):
"""
:type A: List[int]
:type m: int
:type B: List[int]
:type n: int
:rtype: None Do not return anything, modify A in-place instead.
"""
A[m:] = B
A.sort()
return A
思路解析：最直观的方法是先将数组 BB 放进数组 AA 的尾部，然后直接对整个数组进行排序。
复杂度分析：
时间复杂度：O((m+n)log(m+n))。 排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log(m+n))。
空间复杂度：O(log(m+n))。 排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log(m+n))。
示例代码2（双指针）：
class Solution(object):
def merge(self, A, m, B, n):
"""
:type A: List[int]
:type m: int
:type B: List[int]
:type n: int
:rtype: None Do not return anything, modify A in-place instead.
"""
a, b = 0, 0
sorted = []
while a < m or b < n:
if a == m:
sorted.append(B[b])
b += 1
elif b == n:
sorted.append(A[a])
a += 1
elif A[a] < B[b]:
sorted.append(A[a])
a += 1
else:
sorted.append(B[b])
b += 1
A[:] = sorted
思路解析：
方法一没有利用数组 A 与 B 已经被排序的性质。为了利用这一性质，可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。
复杂度分析：
时间复杂度：O(m+n)。 指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
空间复杂度：O(m+n)。 需要建立长度为 m+n 的中间数组sorted。
示例代码3（逆向双指针）：
class Solution(object):
def merge(self, A, m, B, n):
"""
:type A: List[int]
:type m: int
:type B: List[int]
:type n: int
:rtype: None Do not return anything, modify A in-place instead.
"""
a, b = m-1, n-1
tail = n+m-1
while a >=0 or b >= 0:
if a == -1:
A[tail] = B[b]
b -= 1
elif b == -1:
A[tail] = A[a]
a -= 1
elif A[a] < B[b]:
A[tail] = B[b]
b -= 1
else:
A[tail] = A[a]
a -= 1
tail -= 1
思路解析：
方法二中，之所以要使用临时变量，是因为如果直接合并到数组 A 中，A 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 A 中的元素呢？观察可知，A 的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进 A 的最后面。
复杂度分析：
时间复杂度：O(m+n)。 指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
空间复杂度：O(1)。 直接对数组 A 原地修改，不需要额外空间。
