合并排序的数组

给定两个排序后的数组  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]
说明:  A.length  ==  n  +  m

方法一：类似归并排序，使用双指针

def merge(A: List[int], m: int, B: List[int], n: int) -> None:
    C = []
    i = j = 0
    while i <= m - 1 and j <= n - 1:
        if A[i] <= B[j]:
            C.append(A[i])
            i += 1
        else:
            C.append(B[j])
            j += 1
    while i <= m - 1:
        C.append(A[i])
        i += 1
    while j <= n - 1:
        C.append(B[j])
        j += 1
    for i in range(0, n + m):
        A[i] = C[i]

方法二：类似插入排序

def merge2(A: List[int], m: int, B: List[int], n: int) -> None:
    i = 0
    for end_index in range(m - 1, m + n - 1):
        current = B[i]
        pre_index = end_index
        while pre_index >= 0 and A[pre_index] >= current:
            A[pre_index + 1] = A[pre_index]
            pre_index -= 1
        A[pre_index + 1] = current
        i += 1

力扣原题链接：https://leetcode-cn.com/problems/sorted-merge-lcci/