DATA STRUCTURES • ALGORITHMS

Merge Sorted Arrays

Combining two pre-sorted arrays into a single sorted array. This can be done in-place if the first array has sufficient trailing space.

Time

O(N + M)

Space

O(1) (In-place)

Key Principle 1

Two-pointer comparison

Key Principle 2

Back-to-front merging (to avoid overwriting)

Key Principle 3

Maintain three pointers (p1, p2, pMerge)

Key Principle 4

Optimal O(N+M) time complexity

MERGE_SORTED_LAB
NUMS1:
NUMS2:
Current Step
Merging nums2 into nums1 from the back. O(1) extra space.
Playback
Pointer Locations ⠿
P1 (nums1)2
P2 (nums2)2
P (target)5
In-Place Merge ⠿
1int p1 = m - 1, p2 = n - 1, p = m + n - 1;
2while (p2 >= 0) {
3    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
4        nums1[p--] = nums1[p1--];
5    } else {
6        nums1[p--] = nums2[p2--];
7    }
8}
nums1 (capacity 6)
1
0
2
1
3
P1
Ø
3
Ø
4
Ø
P
nums2
2
0
5
1
6
P2

Loading Lab...