DSA Tracker

Visualize

Merge Sorted Array

Fill nums1 from the back so nothing unread is overwritten

time O(m + n)space O(1)

Both inputs are already sorted, so the largest value left anywhere is always sitting at one of the two tails — one comparison per slot is enough, no sorting required. The trick is the direction: writing the merged result forwards would land on nums1 values that have not been read yet, so you would need a copy of nums1 to work from. Writing backwards fills the spare slots at the end first, and the write pointer can never catch up with the read pointer, so the whole merge fits in the array you were given.

Details

Animated on: nums1 = [1,3,5] with 3 spare slots at the end, nums2 = [2,4,6] — merge nums2 into nums1 in place. Spare or stale slots are drawn as _.

Problem:Merge Sorted ArrayEasy

Fill nums1 from the back so nothing unread is overwritten

step 1 / 12

1
[0]
3
[1]
5
[2]
_
[3]
_
[4]
_
[5]

nums1 already owns 6 slots but only 3 hold values, so indices 3..5 are free. Filling from the BACK (k=5) writes into that free space, so nothing unread is ever overwritten — merging forwards would have to shove nums1's own values out of the way first.

  • i=2· arr[2] = 5
  • k=5· arr[5] = _
Pseudocode
1FUNCTION merge(nums1, m, nums2, n)
2  i <- m - 1
3  j <- n - 1
4  k <- m + n - 1
5  WHILE j >= 0
6    IF i >= 0 AND nums1[i] > nums2[j]
7      nums1[k] <- nums1[i]
8      i <- i - 1
9    ELSE
10      nums1[k] <- nums2[j]
11      j <- j - 1
12    k <- k - 1

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. nums1 already owns 6 slots but only 3 hold values, so indices 3..5 are free. Filling from the BACK (k=5) writes into that free space, so nothing unread is ever overwritten — merging forwards would have to shove nums1's own values out of the way first.
  2. Both lists are sorted, so the largest remaining value is at one of the two tails: nums1[2]=5 or nums2[2]=6. 5 < 6, so nums2[2] wins slot 5.
  3. Placed 6 at index 5. nums2 has 2 values left. Tail so far: [6].
  4. Both lists are sorted, so the largest remaining value is at one of the two tails: nums1[2]=5 or nums2[1]=4. 5 > 4, so nums1[2] wins slot 4.
  5. Placed 5 at index 4. Index 4 was free, and index 2 now holds a stale copy nobody will read again — i only ever moves left. Tail so far: [5, 6].
  6. Both lists are sorted, so the largest remaining value is at one of the two tails: nums1[1]=3 or nums2[1]=4. 3 < 4, so nums2[1] wins slot 3.
  7. Placed 4 at index 3. nums2 has 1 value left. Tail so far: [4, 5, 6].
  8. Both lists are sorted, so the largest remaining value is at one of the two tails: nums1[1]=3 or nums2[0]=2. 3 > 2, so nums1[1] wins slot 2.
  9. Placed 3 at index 2. Index 2 was free, and index 1 now holds a stale copy nobody will read again — i only ever moves left. Tail so far: [3, 4, 5, 6].
  10. Both lists are sorted, so the largest remaining value is at one of the two tails: nums1[0]=1 or nums2[0]=2. 1 < 2, so nums2[0] wins slot 1.
  11. Placed 2 at index 1. nums2 is empty now. Tail so far: [2, 3, 4, 5, 6].
  12. j has run out, so every nums2 value is placed. Whatever nums1 still holds at index 0 is smaller than everything written and already sits at the front, so it never has to move — that is why an exhausted nums1 needs a copy loop but an exhausted nums2 does not. Merged: [1, 2, 3, 4, 5, 6].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Merge Sorted Array in the editorAll Arrays problemsBack to roadmap