Merge Sorted Arrays Without Extra Space

Given two sorted arrays arr1 of size $n$ and arr2 of size $m$, the goal is to merge their elements such that the first $n$ smallest elements reside in arr1 in sorted order, and the remaining $m$ elements reside in arr2 in sorted order. The re-arrangement must be achieved in-place without allocating any external array space ($O(1)$ auxiliary space).

1. Problem Breakdown & Re-arrangement Logic

When given two sorted arrays, merging them typically implies creating a single combined sequence. However, under the constraint of no extra space, we must rearrange the elements directly inside the original arrays.

Example Scenario

• Input:

  • arr1[] = {1, 3, 5, 7}, $n = 4$
  • arr2[] = {0, 2, 6, 8, 9}, $m = 5$

• Virtual Merged State (if combined): {0, 1, 2, 3, 5, 6, 7, 8, 9}

• Expected Output (partitioned back into arr1 and arr2):

  • arr1[] = {0, 1, 2, 3} (First $n$ elements)
  • arr2[] = {5, 6, 7, 8, 9} (Remaining $m$ elements)

2. Conceptual Mental Model

To solve this without extra storage, consider the structural placement of elements across the boundary separating arr1 and arr2:

• Core Invariant: All elements in arr1 must be smaller than or equal to all elements in arr2.
• Target Condition: Once every element in arr1 is $\le$ every element in arr2, sorting each array independently restores global sorted order across both arrays without requiring an auxiliary data structure.

3. Naive Approach: Using an Auxiliary Array

The naive intuition utilizes two pointers to merge both sorted arrays into a temporary array arr3 of size $n + m$, and then copies the elements back into arr1 and arr2.

Execution Walkthrough

Vertical Pointer Flow

4. Code & Complexity Analysis: Naive Approach

C++ Implementation

#include <vector>
#include <iostream>

void mergeNaive(std::vector<int>& arr1, std::vector<int>& arr2, int n, int m) {
    std::vector<int> arr3(n + m);
    int left = 0;
    int right = 0;
    int index = 0;

    // Step 1: Merge elements into arr3 using two pointers
    while (left < n && right < m) {
        if (arr1[left] <= arr2[right]) {
            arr3[index++] = arr1[left++];
        } else {
            arr3[index++] = arr2[right++];
        }
    }

    // Copy remaining elements from arr1, if any
    while (left < n) {
        arr3[index++] = arr1[left++];
    }

    // Copy remaining elements from arr2, if any
    while (right < m) {
        arr3[index++] = arr2[right++];
    }

    // Step 2: Write back elements to arr1 and arr2
    for (int i = 0; i < n + m; i++) {
        if (i < n) {
            arr1[i] = arr3[i];
        } else {
            arr2[i - n] = arr3[i]; // Mapping index to second array
        }
    }
}

Complexity

• Time Complexity: $O(n + m) + O(n + m) = O(n + m)$
  • Traversing both arrays to fill arr3 takes $O(n + m)$ time.
  • Copying elements back takes $O(n + m)$ time.
• Space Complexity: $O(n + m)$ auxiliary space due to arr3.

5. Optimal Solution 1: Left-Right Two-Pointer Swap & Sort

To eliminate extra space, swap misallocated elements directly between arrays using the boundary invariant.

Conceptual Insight

• The largest elements of arr1 reside near its end (n - 1).
• The smallest elements of arr2 reside near its beginning (0).
• If arr1[left] (starting at n - 1) is greater than arr2[right] (starting at 0), they are on the wrong sides of the partition boundary and must be swapped.

arr1: [1, 3, 5, 7]        arr2: [0, 2, 6, 8, 9]
                ^                ^
             left = n-1       right = 0
             (Largest)        (Smallest)

Step-by-Step Algorithm

1. Initialize left = n - 1 (last element of arr1) and right = 0 (first element of arr2).
2. Compare arr1[left] and arr2[right]:
   • If arr1[left] > arr2[right]: Swap them, decrement left--, increment right++.
   • If arr1[left] <= arr2[right]: Break early. Since both arrays are individually sorted, all elements to the left of left in arr1 are smaller than arr1[left], and all elements to the right of right in arr2 are larger than arr2[right].
3. Sort arr1 and arr2 individually to restore sorted order inside each partition.

6. Step-by-Step Simulation: Optimal Solution 1

Using arr1 = {1, 3, 5, 7} and arr2 = {0, 2, 6, 8, 9}:

Implementation (C++)

#include <vector>
#include <algorithm>

void mergeOptimal1(std::vector<int>& arr1, std::vector<int>& arr2, int n, int m) {
    int left = n - 1;
    int right = 0;

    // Swap elements if they belong to the other partition
    while (left >= 0 && right < m) {
        if (arr1[left] > arr2[right]) {
            std::swap(arr1[left], arr2[right]);
            left--;
            right++;
        } else {
            // Early break because arrays are sorted
            break;
        }
    }

    // Re-sort individual arrays to maintain intra-array order
    std::sort(arr1.begin(), arr1.end());
    std::sort(arr2.begin(), arr2.end());
}

Complexity

• Time Complexity: $O(\min(n, m)) + O(n \log n) + O(m \log m)$
  • Swapping loop runs at most $\min(n, m)$ times.
  • Sorting arr1 takes $O(n \log n)$ and arr2 takes $O(m \log m)$.
• Space Complexity: $O(1)$ auxiliary space.

7. Optimal Solution 2: The Gap Method (Shell Sort Intuition)

The second optimal solution uses the Gap Method, derived from the Shell Sort algorithm. It works by comparing and swapping elements that are a fixed distance ("gap") apart, gradually reducing the gap until it reaches 1.

Derivation of Gap Formula

1. Total elements = $n + m$.
2. Initial gap = $\lceil (n + m) / 2 \rceil$.
3. Integer representation of ceiling division:

4. In each iteration, after processing all pairs at the current gap distance, reduce the gap:

5. The process terminates after the pass with gap = 1 finishes.

8. Index Mapping Across Two Virtual Arrays

Since arr1 and arr2 are physically distinct memory blocks, we treat them as a single logical array of length $n + m$ using conditional index translation:

Logical Array Indexing:
0 .............. n-1 | n .............. n+m-1
[     arr1     ]     | [     arr2     ]

Pointer Traversal Rules

When given a pointer at logical index idx:

1. idx < n: Refers to arr1[idx].
2. idx >= n: Refers to arr2[idx - n].

This gives three index interaction cases for pointers left and right = left + gap:

Case 1: Both in arr1
left < n  AND  right < n
Compare: arr1[left] vs arr1[right]

Case 2: left in arr1, right in arr2
left < n  AND  right >= n
Compare: arr1[left] vs arr2[right - n]

Case 3: Both in arr2
left >= n AND right >= n
Compare: arr2[left - n] vs arr2[right - n]

9. Step-by-Step Simulation of the Gap Method

• arr1 = {1, 3, 5, 7} ($n = 4$)
• arr2 = {0, 2, 6, 8, 9} ($m = 5$)
• Total Length $n + m = 9$.

Pass 1: gap = ceil(9 / 2) = 5

• left = 0, right = 5
  • arr1[0] (1) vs arr2[1] (2) $\rightarrow 1 \le 2$, no swap.
• left = 1, right = 6
  • arr1[1] (3) vs arr2[2] (6) $\rightarrow 3 \le 6$, no swap.
• left = 2, right = 7
  • arr1[2] (5) vs arr2[3] (8) $\rightarrow 5 \le 8$, no swap.
• left = 3, right = 8
  • arr1[3] (7) vs arr2[4] (9) $\rightarrow 7 \le 9$, no swap.
• right reaches index 9 (out of bounds). Pass ends.

Pass 2: gap = ceil(5 / 2) = 3

• left = 0, right = 3
  • arr1[0] (1) vs arr1[3] (7) $\rightarrow 1 \le 7$, no swap.
• left = 1, right = 4
  • arr1[1] (3) vs arr2[0] (0) $\rightarrow 3 > 0$, SWAP!
  • arr1 becomes {1, 0, 5, 7}, arr2 becomes {3, 2, 6, 8, 9}.
• left = 2, right = 5
  • arr1[2] (5) vs arr2[1] (2) $\rightarrow 5 > 2$, SWAP!
  • arr1 becomes {1, 0, 2, 7}, arr2 becomes {3, 5, 6, 8, 9}.
• left = 3, right = 6
  • arr1[3] (7) vs arr2[2] (6) $\rightarrow 7 > 6$, SWAP!
  • arr1 becomes {1, 0, 2, 6}, arr2 becomes {3, 5, 7, 8, 9}.
• Subsequent comparisons for gap = 3 require no further swaps.

Pass 3: gap = ceil(3 / 2) = 2

Swaps correct smaller localized inversions.

Pass 4: gap = ceil(2 / 2) = 1

Runs adjacent comparisons across the virtual array. Replaces all remaining inversion pairs.

Final Result:

• arr1 = {0, 1, 2, 3}
• arr2 = {5, 6, 7, 8, 9}

10. Code Implementation: Gap Method

#include <vector>
#include <algorithm>

// Helper function to swap elements if left_val > right_val
void swapIfGreater(std::vector<int>& arr1, std::vector<int>& arr2, int ind1, int ind2, int n) {
    // Resolve pointer ind1
    int val1 = (ind1 < n) ? arr1[ind1] : arr2[ind1 - n];
    // Resolve pointer ind2
    int val2 = (ind2 < n) ? arr1[ind2] : arr2[ind2 - n];

    if (val1 > val2) {
        if (ind1 < n && ind2 < n) {
            std::swap(arr1[ind1], arr1[ind2]);
        } else if (ind1 < n && ind2 >= n) {
            std::swap(arr1[ind1], arr2[ind2 - n]);
        } else {
            std::swap(arr2[ind1 - n], arr2[ind2 - n]);
        }
    }
}

void mergeOptimal2_GapMethod(std::vector<int>& arr1, std::vector<int>& arr2, int n, int m) {
    int len = n + m;
    int gap = (len / 2) + (len % 2); // Equivalent to ceil(len / 2.0)

    while (gap > 0) {
        int left = 0;
        int right = left + gap;

        while (right < len) {
            swapIfGreater(arr1, arr2, left, right, n);
            left++;
            right++;
        }

        if (gap == 1) break; // Terminate after completing gap = 1
        gap = (gap / 2) + (gap % 2); // Calculate next ceiling gap
    }
}

Python Implementation

def merge_optimal2_gap_method(arr1: list[int], arr2: list[int], n: int, m: int) -> None:
    def swap_if_greater(ind1: int, ind2: int) -> None:
        # Determine actual references
        val1 = arr1[ind1] if ind1 < n else arr2[ind1 - n]
        val2 = arr1[ind2] if ind2 < n else arr2[ind2 - n]
        
        if val1 > val2:
            if ind1 < n and ind2 < n:
                arr1[ind1], arr1[ind2] = arr1[ind2], arr1[ind1]
            elif ind1 < n and ind2 >= n:
                arr1[ind1], arr2[ind2 - n] = arr2[ind2 - n], arr1[ind1]
            else:
                arr2[ind1 - n], arr2[ind2 - n] = arr2[ind2 - n], arr2[ind1 - n]

    length = n + m
    gap = (length // 2) + (length % 2)

    while gap > 0:
        left = 0
        right = left + gap

        while right < length:
            swap_if_greater(left, right)
            left += 1
            right += 1

        if gap == 1:
            break
        gap = (gap // 2) + (gap % 2)

11. Comparative Analysis

12. Edge Cases & Debugging Pitfalls

Note: Pay close attention to these scenarios during technical interviews:

1. gap = 1 Infinite Loop Bug:

   • Issue: ceil(1 / 2) = 1. If you update gap = (gap / 2) + (gap % 2) without an explicit break condition, the gap remains 1 forever.
   • Fix: Always check if (gap == 1) break; immediately after completing the gap = 1 pass, or break when gap attempts to update past 1.

2. Index Mapping Off-By-One Errors:

   • When right >= n, accessing arr2 requires right - n. Using right directly will throw an out-of-bounds exception.

3. Disjoint Arrays:

   • Example: arr1 = {1, 2, 3}, arr2 = {4, 5, 6}.
   • Both optimal algorithms should correctly perform zero swaps and leave the input unchanged without performance overhead.

Summary and Key Takeaways

• Problem Goal: Merge two sorted arrays arr1 ($n$) and arr2 ($m$) in-place so that arr1 gets the smallest $n$ elements and arr2 gets the remaining $m$ elements, both sorted.
• Naive Solution: Merge elements into an auxiliary array of size $n+m$ using two pointers, then copy back. Costs $O(n+m)$ time and $O(n+m)$ space.
• Optimal 1 (Swap & Sort): Start left at $n-1$ (arr1) and right at $0$ (arr2). Swap whenever arr1[left] > arr2[right], then move left-- and right++. Once arr1[left] <= arr2[right], stop swapping and sort each array independently. Time: $O(\min(n, m) + n \log n + m \log m)$, Space: $O(1)$.
• Optimal 2 (Gap Method): Uses Shell Sort intuition. Define gap = ceil((n + m) / 2) and compare elements that are gap positions apart across the combined array.
• Virtual Index Translation: Convert a logical index idx in range $[0, n+m-1]$ to physical arrays: access arr1[idx] if idx < n, else access arr2[idx - n].
• Gap Reduction: Update gap = ceil(gap / 2) using integer arithmetic (gap / 2) + (gap % 2).
• Termination Condition: Explicitly stop the Gap Method loop after completing the iteration where gap == 1 to prevent infinite loops. Time: $O((n+m) \log(n+m))$, Space: $O(1)$.