Pattern visualizer
Merge Sorted Arrays
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. 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 _..
Fill nums1 from the back so nothing unread is overwritten
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.
1FUNCTION merge(nums1, m, nums2, n)2 i <- m - 13 j <- n - 14 k <- m + n - 15 WHILE j >= 06 IF i >= 0 AND nums1[i] > nums2[j]7 nums1[k] <- nums1[i]8 i <- i - 19 ELSE10 nums1[k] <- nums2[j]11 j <- j - 112 k <- k - 1
← / → step · space play · Home restart