I ran the merge twice on the same inputs: once with the output buffer sized up front, once with Vec::new(). Same answer both times, and the second one reallocated its way there.

The merge is a two-pointer loop. Everyone writes that part the same way. The part worth looking at is the line that creates the output:

let mut res = Vec::with_capacity(nums1.len() + nums2.len());

The merged array has a known length before a single element has been compared. It is nums1.len() + nums2.len(), always. Nothing about the merge can change that. So the buffer is sized correctly on the first allocation and never touched again.

Without that line, Vec::new() starts with no buffer at all, and the first push allocates four elements, the fifth reallocates to eight, the ninth reallocates to sixteen, and so on. I measured it. For a six-element result, the buffer changed twice. For a thousand elements, it changed nine times. Every change after the first is a copy of the elements already merged.

The difference is not abstract. Here is the same merge both ways, on the same inputs:

merged: [1, 2, 2, 3, 5, 6] len=6 capacity=6
expected capacity = 3+3 = 6
no-capacity merged: [1, 2, 2, 3, 5, 6] len=6 capacity=8
1000+1000 -> len=2000 capacity=2000
no-capacity 1000+1000 -> len=2000 capacity=2048

Both produce the same answer. One ends with a buffer exactly the size of the answer. The other ends with two spare elements for six inputs, and 48 spare elements for two thousand.

Two pointers and a buffer

pub fn merge(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
    let (mut left, mut right) = (0, 0);
    let mut res = Vec::with_capacity(nums1.len() + nums2.len());

    while left < nums1.len() && right < nums2.len() {
        if nums1[left] <= nums2[right] {
            res.push(nums1[left]);
            left += 1;
        } else {
            res.push(nums2[right]);
            right += 1;
        }
    }

    res.extend_from_slice(&nums1[left..]);
    res.extend_from_slice(&nums2[right..]);

    res
}

let (mut left, mut right) = (0, 0); destructures a tuple into two mutable bindings. It is not required here, and it is not faster than two separate lets. It is a way of saying that these two counters are one concept with two halves, which is exactly what they are: the read positions in the two inputs, advancing independently but always in step with the merge.

The while loop compares the fronts of both inputs and takes the smaller one. It exits as soon as one input is exhausted, and the two extend_from_slice calls handle the leftovers.

The tail copies in one go

The leftovers could be copied with a for loop and a push. extend_from_slice is better because of what it does underneath. I followed it through the standard library source for rustc 1.98.1:

extend_from_slice calls self.spec_extend(other.iter()). slice::Iter hits a specialization of SpecExtend for T: TrivialClone, which calls append_elements(slice). And append_elements is this:

unsafe fn append_elements(&mut self, other: *const [T]) {
    let count = other.len();
    self.reserve(count);
    let len = self.len();
    if count > 0 {
        unsafe {
            ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count)
        };
    }
    self.len += count;
}

One ptr::copy_nonoverlapping for the whole tail. Not a per-element loop with a capacity check on each step, not a push that has to decide whether it can grow the buffer. A single copy of a contiguous range into contiguous spare capacity.

And self.reserve(count) is a no-op here, because the buffer was sized for exactly this. The two calls and the loop’s pushes together add up to nums1.len() + nums2.len() elements, which is what the buffer was allocated for. The capacity never changes after the first allocation.

When one input is exhausted, the other one’s slice is empty, count is zero, and the if count > 0 guard skips the copy entirely. Merging two empty vectors returns an empty vector with capacity zero, and merging [1] with [] returns a vector of capacity one. The allocation discipline holds at the edges too.

Both inputs are consumed

merge takes both vectors by value, so the caller hands over ownership. The merge cannot mutate them in place, and it does not try. The result is a fresh buffer, and the two inputs are dropped when the function returns. This is the ownership model doing real work: the function signature says exactly what it consumes and what it produces, and there is no reference to track and no lifetime to reason about.

This is also the one place where a Rust solution would look different from the same algorithm in a language with cheaper allocation. with_capacity is not free. You are telling the allocator the exact size before you know whether the algorithm will succeed. If the merge could fail halfway, that buffer would be wasted work. Here it cannot fail, the length is fixed by the inputs, and asking once is strictly cheaper than asking repeatedly and being wrong.

Size it before you start

Sizing a container from information you already have is one of the cheapest optimizations in any language, and one of the easiest to forget. The cost of getting it wrong is not a single slow run. It is a buffer that reallocates several times on the way to its final size, copying everything merged so far each time, with the spare capacity at the end holding memory nobody asked for.

The merge itself did not need to be clever. It needed the output size to be known before the output started.

The habit I want out of this one is narrow: when the length of the output is a function of the length of the inputs, write that line before the loop. I still catch myself sizing the container after the loop, when the answer was sitting in the input lengths the whole time.


Next: In Place, and the Borrow Checker Agreed