Cracking The Coding Interview Together – Problem 10.1: Sorted Merge

Have you ever tried to move furniture into a room while you are already standing inside it? If you start pushing things from the front, you end up blocking the doorway, crushing your shins, and realizing you should have planned the logistics from the back wall forward. Array manipulation in-place often mimics this exact spatial nightmare.

When we encounter array-based problems in systems design or coding interviews, our initial instinct usually points us toward allocating a fresh buffer and copying things over. But what happens when hardware constraints, memory footprints, or strict API contracts demand that we do it in place with zero extra allocations? Today, we are tackling Problem 10.1: Sorted Merge from Cracking the Coding Interview. By the end of this article, you and I will dismantle this problem, optimize our pointer logic, and write production-grade Java code that handles memory like a senior systems engineer.

Problem Statement

You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

Let us define our operational goals clearly:

• We are given array A of size n + m, which contains only n valid elements stored at the beginning, followed by m empty buffer slots (often represented as zeros, nulls, or default values).
• Array B has size m and contains all valid, sorted elements.
• We must merge B into A such that the final combined array of size n + m is completely sorted.
• The operation must happen in-place within array A.

Analyze the Problem Together

Let us break down the constraints and find the "Aha!" conflict. If we look at how standard sorting or merging algorithms work—like the merge step in Merge Sort—we naturally want to compare elements starting from index 0 and move forward. Let us see why that fails us here.

If we place pointers at the beginning of array A and array B, and we find that B[0] is smaller than A[0], we need to insert B[0] into the front of A. But array elements are contiguous blocks in memory! To insert an element at index 0 of array A, we have to shift every single existing element in A one position to the right. Doing this for multiple elements results in a catastrophic time complexity of \(O(n \times m)\).

Here is our architectural breakthrough: What if we merge from the back instead of the front?

Think about the physical layout of array A. The end of array A is completely empty—it is a buffer waiting to be filled. The largest elements from both array A (at index n-1) and array B (at index m-1) belong at the very end of the combined array (at index n + m - 1). By working backwards from the largest elements to the smallest, we never overwrite any valid data in A that we haven't already processed. This eliminates shifting entirely.

Questions for the Interviewer

Before writing a single line of code, a senior engineer establishes boundaries by asking clarifying questions:

• "Are the arrays sorted in ascending or descending order?" (We will assume ascending order for this implementation).
• "How are the empty slots in array A represented? Are they explicitly designated by an integer variable n, or do we scan for null/default values?"
• "Can array B be null or empty, and how should we handle edge cases where array A has no initial elements?"
• "Are there any concurrency guarantees we need to worry about, or is this a synchronous single-threaded utility method?"

Think About the Solution

Let us design our high-level architecture. We need three pointers:

• indexA: Points to the last valid element in array A (which is at index n - 1).
• indexB: Points to the last valid element in array B (which is at index m - 1).
• mergedIndex: Points to the absolute end of the buffer in array A (which is at index n + m - 1).

In each iteration, we compare A[indexA]` and B[indexB]. Whichever element is larger gets placed at A[mergedIndex], and we decrement that element's pointer alongside mergedIndex. We continue this loop until we have exhausted all elements in array B. If array A runs out of elements first, we simply copy the remaining elements of array B into the front of array A.

Write Code and Explain

Here is the production-ready Java implementation for the sorted merge problem.

public class ArrayMerger {

    /**
     * Merges sorted array B into sorted array A in-place.
     * 
     * @param a      The array containing valid elements and a buffer at the end.
     * @param countA The number of valid elements currently in array a.
     * @param b      The second sorted array to be merged.
     * @param countB The number of valid elements in array b.
     */
    public static void merge(int[] a, int countA, int[] b, int countB) {
        // Pointer for the last valid element in array A
        int indexA = countA - 1;
        
        // Pointer for the last valid element in array B
        int indexB = countB - 1;
        
        // Pointer for the final merged position at the end of array A's buffer
        int mergedIndex = countA + countB - 1;

        // Merge elements by comparing from back to front
        while (indexA >= 0 && indexB >= 0) {
            if (a[indexA] > b[indexB]) {
                a[mergedIndex] = a[indexA];
                indexA--;
            } else {
                a[mergedIndex] = b[indexB];
                indexB--;
            }
            mergedIndex--;
        }

        // If there are remaining elements in B, copy them over.
        // Note: If elements remain in A, they are already in their correct sorted positions.
        while (indexB >= 0) {
            a[mergedIndex] = b[indexB];
            indexB--;
            mergedIndex--;
        }
    }
}

Let us walk through the execution step by step:

1. We initialize our pointers. indexA points to n-1, indexB points to m-1, and mergedIndex points to n + m - 1.
2. The while loop runs as long as both indexA and indexB are greater than or equal to zero. Inside, we compare the elements at A[indexA] and B[indexB].
3. If A[indexA] is greater, we copy it into A[mergedIndex] and decrement indexA. Otherwise, we take B[indexB], place it into A[mergedIndex], and decrement indexB.
4. Regardless of which array supplied the element, we decrement mergedIndex to prepare for the next placement.
5. Once array A is exhausted (meaning indexA < 0), any remaining elements in B are strictly smaller than everything processed so far. We sweep them into A using a secondary clean-up loop. If array B exhausts first, the loop terminates immediately because the remaining elements in A are already correctly placed.

Time & Space Complexity

Let us analyze our resource consumption:

• Time Complexity: \(O(n + m)\). We traverse each element in array A and array B at most once. There are no nested loops or shifting operations. This is optimal.
• Space Complexity: \(O(1)\). We perform the entire merge operation in-place using only a few primitive pointer variables, satisfying the strictest memory constraints.

Why This Problem Matters (The Senior Perspective)

At first glance, Problem 10.1 feels like a basic array manipulation exercise. However, the underlying principle—working backwards from an output buffer—is a foundational pattern in systems engineering.

You see this exact technique applied in high-performance memory buffers, string manipulation algorithms (like in-place URL encoding or reversing words in a buffer), and database record merging algorithms where disk blocks are read sequentially. Understanding how to manage pointers in bounded memory prevents unnecessary garbage collection pressure and avoids costly CPU cache misses caused by random memory shifting.

Final Thoughts

In-place array manipulation teaches us to look past our initial linear habits and examine the spatial layout of our data. By shifting our perspective from the front to the back, we turned an \(O(n \times m)\) bottleneck into a sleek, linear \(O(n + m)\) solution.

Take some time to experiment with edge cases—what happens if array B contains elements smaller than all elements in A? Write a quick unit test suite to verify your logic. Keep building, stay curious, and I will see you in the next breakdown!