Merge Two Sorted Arrays In-Place: Fill From the Back

• In-place merge – takes a first array with spare capacity at its end and a second sorted array, merging the second into the first so the result is sorted, without allocating a separate output array.
• Write from the back – three pointers start at the last real element of each input and the very end of the first array; the larger tail element is placed at the write position, moving backward.
• O(m + n) time, O(1) space – each element is compared and placed exactly once with no extra allocation.
• Stop condition – stop when the second array is fully consumed; leftover first-array elements are already in place.
• Safety invariant – the write pointer is always at or ahead of the read pointer in the first array, so no element is overwritten before it is placed.

What is the merge two sorted arrays in-place problem?

Given two sorted arrays where the first array has enough extra capacity at the end to hold all elements of the second array, merge the second into the first so the combined result is sorted, without using a separate output array. This is the classic merge step from merge sort, adapted for in-place operation.

At the National Bank of India, Rajesh's transaction ledger has spare rows, and Priya's sorted transactions must be merged in without creating a new ledger.

Why write from the back instead of the front?

The obvious approach merges from the front into a new array and copies back, which uses O(n) extra space. Writing from the front into the first array would overwrite elements that have not yet been merged. Writing from the back is safe because the back of the first array is exactly the free space, so you never clobber a value you still need.

Array A (with capacity): [1, 3, 5, _, _, _]  m=3
Array B:                 [2, 4, 6]            n=3

Writing from front: A[0] = min(1,2) = 1, but what if B's element wins?
  A[0] = 2 would overwrite the 1 before it is placed!

Writing from back: A[5] = max(5,6) = 6 → safe, slot was empty
                   A[4] = max(5,4) = 5 → safe, slot was empty
                   A[3] = max(3,4) = 4 → safe, slot was empty
                   ...

How does the algorithm work internally?

Three indices: i starts at the last real element of array A (index m-1), j starts at the last element of array B (index n-1), k starts at the very last slot of array A (index m+n-1).

At each step, compare A[i] and B[j], copy the larger one to A[k], then decrement the source pointer and k. Repeat until j < 0 (second array exhausted).

How do you implement it? (with code)

package com.bank.service;

import java.math.BigDecimal;

public class MergeSortedArrays {

    public static void merge(BigDecimal[] ledger, int m,
                             BigDecimal[] priyaTxns, int n) {
        int i = m - 1;       // last real element in ledger
        int j = n - 1;       // last element in priyaTxns
        int k = m + n - 1;   // last slot in ledger

        while (j >= 0) {
            if (i >= 0 && ledger[i].compareTo(priyaTxns[j]) > 0) {
                ledger[k] = ledger[i];
                i--;
            } else {
                ledger[k] = priyaTxns[j];
                j--;
            }
            k--;
        }
    }

    public static void main(String[] args) {
        BigDecimal[] ledger = new BigDecimal[6];
        ledger[0] = new BigDecimal("100");
        ledger[1] = new BigDecimal("300");
        ledger[2] = new BigDecimal("500");

        BigDecimal[] priya = {
            new BigDecimal("200"),
            new BigDecimal("400"),
            new BigDecimal("600")
        };

        merge(ledger, 3, priya, 3);
        for (BigDecimal b : ledger) {
            System.out.print(b + " ");
        }
    }
}

100 200 300 400 500 600

Why stop when the second array is exhausted?

If array A's elements are exhausted first, the remaining elements of B still need to be copied into the front of A. But if B is exhausted first, the remaining elements of A are already sitting in their correct positions because they were never moved. The loop while (j >= 0) handles both cases: when i < 0, the condition i >= 0 fails and B's elements are copied, which is the copy-remaining step.

What is the write-from-back invariant?

At every moment, the write pointer k is always at or ahead of the read pointer i. This invariant holds because the total number of elements still to place equals the distance from the start to k plus one, which always covers both unread tails. Stating this invariant in an interview demonstrates you understand why the direction matters.

Invariant: k >= i at all times

  k represents: next write position
  i represents: next read position in A
  k - i = (elements remaining in B) >= 0
  So k >= i always holds → no clobbering

How is this different from a standard merge?

| Aspect | Standard merge | In-place merge (back-fill) |
|---|---|---|
| Output | Separate array | First array (with capacity) |
| Direction | Front to back | Back to front |
| Extra space | O(m + n) | O(1) |
| Precondition | None | First array must have capacity for both |
| Which pointer stops first | Either | Stop when second exhausted |

What are the edge cases?

• Second array empty – j starts at -1, loop does not execute, first array is unchanged.
• First array empty – i starts at -1, all of B is copied into the spare slots.
• All elements of B are smaller – B fills the front of the spare space, A's elements stay in place.
• All elements of B are larger – B fills the back, A's elements shift left naturally.

// Edge case: B is empty
merge(ledger, 3, new BigDecimal[0], 0);
// ledger unchanged: [100, 300, 500]

What should a senior engineer know?

A senior engineer should mention stability. When A[i] equals B[j], choosing A[i] first preserves the relative order of equal elements from the original arrays, making the merge stable. For transaction records sorted by date, stability ensures that two transactions on the same date keep their original order.

For money, always compare with BigDecimal.compareTo so amounts are exact.

What are common interview follow-up questions?

• Can you merge without the spare capacity? – You would need O(n) extra space or a more complex gap-based algorithm.
• What about merging K sorted arrays? – Use a min-heap of size K, pulling the smallest head each time.
• Is the merge stable? – Yes, if you break ties by choosing from the first array.