Merge Sorted Array: definition
Merge two sorted arrays into one sorted result. This task uses two read pointers and a write position to fill the first array from the end.
Task example: Merge Sorted Array
The first m values of nums1 and all n values of nums2 are sorted. nums1 has n spare slots at the end. Merge the real values into nums1 in ascending order. Modify the original list; return nothing.
Only the last n positions are spare slots. A zero among the first m values is real data. Either input may have no real values.
Copy and sort: video explanation
nums1 = [1, 2, 3, 0, 0, 0], m = 3 · nums2 = [2, 5, 6], n = 3
Prefer reading? Follow the steps below.
- Copy nums2[j] into nums1[m + j] for each j. This replaces the spare slots with real values.
- Now nums1 is [1, 2, 3, 2, 5, 6]. Call nums1.sort() to reorder it as [1, 2, 2, 3, 5, 6].
- The caller sees the changed list. Assigning a new list only to the local name nums1 would not update the caller’s list.
Time complexity · O(N log N) general bound
N = m + n. Copying is O(n); comparison sorting has an O(N log N) general upper bound. For these two already sorted runs, CPython’s adaptive sort can merge in O(N) time.
Space complexity · O(N)
Python sort may use O(N) temporary workspace. Calling sort on the same list does not guarantee O(1) extra space.
Merge from the end: video explanation
nums1 = [1, 2, 3, 0, 0, 0], m = 3 · nums2 = [2, 5, 6], n = 3
Prefer reading? Follow the steps below.
- Set i = m - 1, j = n - 1, and write = m + n - 1. i and j read real values; write marks the next output position.
- While j >= 0, put the larger remaining value at nums1[write]. Move its read pointer left, then decrease write. Check i >= 0 before reading nums1[i].
- Write 6, then 5, then 3, then 2 from right to left. Once j is -1, stop: the remaining 1 and 2 in nums1 are already correct.
- If i becomes -1 first, copy the remaining nums2 values. If n is zero, no work is needed.
Why it works: the largest unread value belongs at the end. Filling backward protects unread values and grows a sorted suffix. This gives a direct linear merge with constant extra space, without relying on sorting.
Time complexity · O(m + n)
Each step places one value and moves write left. At most m + n positions are filled; n = 0 takes O(1).
Space complexity · O(1)
Only i, j, and write are stored: O(1) extra space. The spare slots already belong to the input.