01: Introduction

Imagine you have two sorted lists of numbers and you want to combine them into one big sorted list. Sounds easy, right? The standard way is to use a third array to store the merged result. But what if you’re not allowed to use that extra memory?

That’s exactly the problem — merge two sorted arrays without extra space in Python. This forces you to work directly inside the original arrays, making it a great test of your understanding of in-place algorithms.

This problem shows up in top company interviews at Amazon, Google, Microsoft, and others because it tests memory awareness — a skill every real-world programmer needs. In embedded systems, mobile apps, or any low-memory environment, allocating extra arrays can be expensive or simply impossible.

02: Problem Statement

Given two sorted arrays arr1 of size n and arr2 of size m, merge them in sorted order such that arr1 holds the first n smallest elements and arr2 holds the remaining m elements. You cannot use any extra space.

Example 1

Input:  arr1 = [1, 3, 5]   arr2 = [2, 4, 6]
Output: arr1 = [1, 2, 3]   arr2 = [4, 5, 6]

Example 2

Input:  arr1 = [10, 12]   arr2 = [5, 18, 20]
Output: arr1 = [5, 10]    arr2 = [12, 18, 20]

Input Format

1. First line: size of arr1 (n)
2. Second line: n space-separated integers (arr1)
3. Third line: size of arr2 (m)
4. Fourth line: m space-separated integers (arr2)

Output Format

Print both arrays separated by a newline after merging.

Constraints

03: Why This Problem Is Important

• Memory optimization — critical in embedded and IoT devices where RAM is limited
• Real-time systems — no time to allocate and free memory dynamically
• Database engines — merge operations on sorted runs during external sort
• Interview filter — companies use this to check if you understand space complexity
• Competitive programming — frequently appears in array/sorting problem sets

04: Naive Approach – Using Extra Space

The simple solution everyone thinks of first: merge both arrays into a third array, sort it (it’s already sorted so you just merge), then copy the first n elements back to arr1 and the remaining m elements to arr2.

# Naive: merge into extra array, copy back
def merge_naive(arr1, arr2):
    n, m = len(arr1), len(arr2)
    temp = []
    i = j = 0
    while i < n and j < m:
        if arr1[i] <= arr2[j]: temp.append(arr1[i]); i += 1
        else: temp.append(arr2[j]); j += 1
    temp += arr1[i:] + arr2[j:]
    arr1[:] = temp[:n]
    arr2[:] = temp[n:]

Optimal Approach 1 – Gap Method (Shell Sort Idea)

This is the best approach. It comes from the idea behind Shell Sort. Instead of comparing adjacent elements, you compare elements that are far apart — at a “gap” distance — and swap them if they’re out of order. The gap keeps shrinking until it becomes 1.

The key insight: treat both arrays as one logical array of size n+m. Compare elements at positions i and i + gap. If the element at the higher index is smaller, swap them. Reduce the gap and repeat.

Optimal Approach 2 – Swap and Sort Method

A simpler (but slightly less efficient) approach: compare the last element of arr1 with the first element of arr2. If arr1[n-1] > arr2[0], swap them. Then sort both arrays individually.

05: Flowchart 

06: Pseudocode – Gap Method

    n = length of arr1
    m = length of arr2
    gap = ceil((n + m) / 2)

    WHILE gap > 0:
        i = 0
        j = gap

        WHILE j < n + m: IF i is in arr1 AND j is in arr2: compare arr1[i] with arr2[j - n] ELSE IF both i and j in arr2: compare arr2[i - n] with arr2[j - n] ELSE: compare arr1[i] with arr1[j] IF left element > right element:
                SWAP them

            i = i + 1
            j = j + 1

        IF gap == 1:
            gap = 0
        ELSE:
            gap = ceil(gap / 2)

    RETURN arr1, arr2

07: Python Program

import math

def get_element(arr1, arr2, index, n):
    # Treat arr1 + arr2 as one logical array
    if index < n:
        return arr1[index]
    return arr2[index - n]

def set_element(arr1, arr2, index, n, value):
    if index < n:
        arr1[index] = value
    else:
        arr2[index - n] = value

def merge_without_space(arr1, arr2):
    n = len(arr1)
    m = len(arr2)

    # Start with gap = ceil((n+m) / 2)
    gap = math.ceil((n + m) / 2)

    while gap > 0:
        i, j = 0, gap

        while j < n + m:
            left  = get_element(arr1, arr2, i, n)
            right = get_element(arr1, arr2, j, n)

            # If left element is greater, swap them
            if left > right:
                set_element(arr1, arr2, i, n, right)
                set_element(arr1, arr2, j, n, left)

            i += 1
            j += 1

        # Reduce gap; stop when gap becomes 0
        if gap == 1:
            gap = 0
        else:
            gap = math.ceil(gap / 2)


n = int(input("Enter size of arr1: "))
arr1 = list(map(int, input("Enter arr1 elements: ").split()))

m = int(input("Enter size of arr2: "))
arr2 = list(map(int, input("Enter arr2 elements: ").split()))

merge_without_space(arr1, arr2)

print("arr1:", arr1)
print("arr2:", arr2)

09: Dry Run – Step by Step

Let’s trace through with arr1 = [1, 3, 5], arr2 = [2, 4, 6]. Combined logical array: [1, 3, 5 | 2, 4, 6], n=3, m=3, total=6.

10: Time & Space Complexity

11: Test Cases

12: Edge Cases to Watch For

• Empty array — if either array is empty, the other stays unchanged. Your loop simply won’t execute meaningful swaps.
• Single element — gap starts at 1, one comparison happens. Works correctly.
• All same elements — comparisons never trigger swaps. Final result is unchanged and already correct.
• Reverse sorted inputs — the gap method handles this since it doesn’t rely on input order assumptions.

13: Mistakes Beginners Make

• Using an extra array — this solves nothing and fails the constraint
• Wrong ceiling division — using gap // 2 instead of math.ceil(gap / 2) breaks the algorithm
• Off-by-one in index mapping — forgetting that arr2 starts at index n in the logical array
• Not handling the gap=1 case — leads to an infinite loop if gap never reaches 0
• Comparing across wrong boundaries — always check which array index i and j belong to

14: Common Interview Questions

15: Real World Uses

• Database engines — sorting and merging sorted runs during merge-sort external sorting
• File systems — merging sorted index blocks without loading them entirely into RAM
• Streaming data — combining two sorted event streams in real-time pipelines
• Compiler symbol tables — merging sorted symbol lists during linking
• Memory-constrained IoT devices — microcontrollers with kilobytes of RAM

16: FAQ

Suggested Reading

• Two Sum Problem in Python – Hash Map Approach
• Binary Search Explained – Every Variant You Need
• Array Rotation Problems – Reverse Method & Juggling
• Largest & Smallest Element in an Array – O(n) Guide