Merge Two Sorted Arrays Without Extra Space in DSA Python

Mental Model

We want to combine two sorted lists into one sorted order without using extra space. We do this by swapping elements between the two lists to keep them sorted.

Analogy: Imagine you have two sorted stacks of books on two tables. Instead of moving books to a new table, you swap books between the tables to keep both stacks sorted.

Array1: [1, 5, 9, 10, 15, 20]
Array2: [2, 3, 8, 13]

Dry Run Walkthrough

Input: array1: [1, 5, 9, 10, 15, 20], array2: [2, 3, 8, 13]

Goal: Merge both arrays so that after merging, array1 and array2 together represent the sorted order without using extra space.

Step 1: Compare arr1[5]=20 > arr2[0]=2, swap them

array1: [1, 5, 9, 10, 15, 2]
array2: [20, 3, 8, 13]

Why: Swap 20 and 2 because 20 > 2 to keep smaller elements in array1

Step 2: Compare arr1[4]=15 > arr2[1]=3, swap them

array1: [1, 5, 9, 10, 3, 2]
array2: [20, 15, 8, 13]

Why: Keep smaller elements in array1 and larger in array2

Step 3: Compare arr1[3]=10 > arr2[2]=8, swap them

array1: [1, 5, 9, 8, 3, 2]
array2: [20, 15, 10, 13]

Why: Continue swapping to maintain order

Step 4: Compare arr1[2]=9 <= arr2[3]=13, no more swaps needed, break

array1: [1, 5, 9, 8, 3, 2]
array2: [20, 15, 10, 13]

Why: arr1[i] <= arr2[j], so remaining elements are in correct relative order

Step 5: Sort both arrays individually after swaps

array1: [1, 2, 3, 5, 8, 9]
array2: [10, 13, 15, 20]

Why: Sorting arrays after swaps ensures final sorted order without extra space

Result:

array1: [1, 2, 3, 5, 8, 9]
array2: [10, 13, 15, 20]

Annotated Code

DSA Python

def merge_without_extra_space(arr1, arr2):
    n, m = len(arr1), len(arr2)
    i, j = n - 1, 0
    while i >= 0 and j < m:
        if arr1[i] > arr2[j]:
            arr1[i], arr2[j] = arr2[j], arr1[i]  # swap bigger in arr1 with smaller in arr2
            i -= 1
            j += 1
        else:
            break  # no more swaps needed if arr1[i] <= arr2[j]
    arr1.sort()  # sort arr1 after swaps
    arr2.sort()  # sort arr2 after swaps


# Driver code
arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
merge_without_extra_space(arr1, arr2)
print('array1:', arr1)
print('array2:', arr2)

while i >= 0 and j < m:

loop to compare elements from end of arr1 and start of arr2

if arr1[i] > arr2[j]:

check if swap is needed to keep smaller elements in arr1

arr1[i], arr2[j] = arr2[j], arr1[i]

swap elements between arrays

i -= 1 j += 1

move pointers inward after swap

else: break

stop if no more swaps needed

arr1.sort() arr2.sort()

sort arrays individually after swaps to finalize order

Output

array1: [1, 2, 3, 5, 8, 9]

array2: [10, 13, 15, 20]

Complexity Analysis

Time: O(n log n + m log m) because sorting both arrays after swapping takes most time

Space: O(1) because no extra space is used except variables for indices

vs Alternative: Naive approach uses extra space to merge arrays, which costs O(n + m) space; this method saves space but requires sorting after swaps.

Edge Cases

One or both arrays empty

Function handles gracefully; sorting empty arrays is safe and no swaps occur

DSA Python

while i >= 0 and j < m:

Arrays already fully sorted with no overlapping elements

No swaps happen; function exits early at break

DSA Python

else:
    break

Arrays with duplicate elements

Duplicates are handled correctly by swaps and sorting

DSA Python

arr1.sort()
arr2.sort()

When to Use This Pattern

When asked to merge two sorted arrays without extra space, use the swapping and sorting pattern to rearrange elements in place efficiently.

Common Mistakes

Mistake: Trying to merge by shifting elements one by one causing O(n*m) time
Fix: Use two pointers from opposite ends and swap, then sort arrays once

Mistake: Not sorting arrays after swaps, resulting in unsorted arrays
Fix: Always sort both arrays after swapping to finalize order

Summary

Merges two sorted arrays into sorted order without extra space by swapping and sorting.

Use when you must merge sorted arrays but cannot use extra memory.

The key is swapping elements from the end of first and start of second array, then sorting both.