Merge Two Sorted Arrays Without Extra Space in DSA Python - Time & Space Complexity

Time Complexity: Merge Two Sorted Arrays Without Extra Space

O(n * m)

Understanding Time Complexity

We want to understand how long it takes to merge two sorted arrays without using extra space.

How does the time needed grow as the arrays get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for i in range(len(arr1)):
    if arr1[i] > arr2[0]:
        arr1[i], arr2[0] = arr2[0], arr1[i]
        # Re-sort arr2 to keep it sorted
        first = arr2[0]
        k = 1
        while k < len(arr2) and arr2[k] < first:
            arr2[k - 1] = arr2[k]
            k += 1
        arr2[k - 1] = first

This code merges two sorted arrays by swapping elements and re-sorting the second array in place.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Outer loop runs over all elements of the first array.
• How many times: For each element in the first array, a possible inner while loop re-sorts part of the second array.

How Execution Grows With Input

As the size of the arrays grows, the outer loop runs once per element in the first array.

The inner while loop can run up to the length of the second array in the worst case.

Input Size (n)	Approx. Operations
10	Up to 100 (10 * 10)
100	Up to 10,000 (100 * 100)
1000	Up to 1,000,000 (1000 * 1000)

Pattern observation: The operations grow roughly with the product of the sizes of the two arrays, meaning it grows quickly as arrays get bigger.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed grows proportionally to the size of the first array times the size of the second array.

Common Mistake

[X] Wrong: "Since both arrays are sorted, merging without extra space is always O(n + m)."

[OK] Correct: The inner re-sorting loop can cause extra work, making the process slower than a simple linear merge.

Interview Connect

Understanding this time complexity helps you explain trade-offs when merging arrays without extra space, a useful skill in interviews and real coding tasks.

Self-Check

"What if we used a gap method to merge the arrays instead? How would the time complexity change?"