合并两个有序数组

题目
给定两个有序正整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小等于 m + n）来保存 nums2 中的元素。
不开辟新的slice临时空间。

思路：归并思想
复杂度分析
时间复杂度：O(m+n)O(m+n)。
指针移动单调递增，最多移动 m+nm+n 次，因此时间复杂度为 O(m+n)O(m+n)。

空间复杂度：O(m+n)O(m+n)。
需要建立长度为 m+nm+n 的中间数组 \textit{sorted}sorted。

func merge(l1 []int, m int, l2 []int, n int) {
    index := m + n - 1
    p1, p2 := m-1, n-1

    for p1 >= 0 && p2 >= 0 {
        if l1[p1] >= l2[p2] {
            l1[index] = l1[p1]
            p1--
        } else {
            l1[index] = l2[p2]
            p2--
        }
        index--
    }

    for p1 >= 0 {
        l1[index] = l1[p1]
        p1--
        index--
    }

    for p2 >= 0 {
        l2[index] = l2[p2]
        p2--
        index--
    }

    fmt.Println(l1)
}

# 开辟新空间
func merge(l1 []int, l2 []int) {
    m1 := len(l1)
    m2 := len(l2)
    p1, p2 := 0, 0
    l := make([]int, 0, m1+m2)

    for {
    //for p1 <= m1 && p2 <= m2 {
        if p1 == m1 {
            l = append(l, l2[p2:]...)
            break
        }
        if p2 == m2 {
            l = append(l, l1[p1:]...)
            break
        }
        if l1[p1] < l2[p2] {
            l = append(l, l1[p1])
            p1++
        } else {
            l = append(l, l2[p2])
            p2++
        }
    }

    fmt.Println(l)
}