Merge Two Sorted Arrays

1. Problem Description

Given two sorted integer arrays and , merge array into array to form a sorted array. Note: You can assume that array A has enough space to hold the elements of array B, and the initial numbers of elements in A and B are and .

2. Approach

1. Approach 1
   • Merge sort Merge Sort
     • From front to back
     • From back to front

3. Implementation

3.1. From Front to Back

// Time: O(N)
// Space: O(N)
func merge(A []int, m int, B []int, n int) {
	res := make([]int, 0)

	i := 0
	j := 0
	for i < m && j < n {
		if A[i] < B[j] {
			res = append(res, A[i])
			i++
		} else {
			res = append(res, B[j])
			j++
		}
	}

	for i < m {
		res = append(res, A[i])
		i++
	}

	for j < n {
		res = append(res, B[j])
		j++
	}

	for i := 0; i < len(res); i++ {
		A[i] = res[i]
	}
}

3.2. From Back to Front

// Time: O(N)
// Space: O(1)
func merge2(A []int, m int, B []int, n int) {
	i, j, k := m-1, n-1, m+n-1
	for i >= 0 && j >= 0 {
		if A[i] > B[j] {
			A[k] = A[i]
			i--
		} else {
			A[k] = B[j]
			j--
		}
		k--
	}
	for i >= 0 {
		A[k] = A[i]
		i--
		k--
	}
	for j >= 0 {
		A[k] = B[j]
		j--
		k--
	}
}

4. References

• Merge Two Sorted Arrays - NowCoder