Python - Merge Two Sorted Arrays without using Extra Space

Python – Merge Two Sorted Arrays Without Using Extra Space

This tutorial explains how to merge two sorted arrays in Python without using any extra space. This problem is often asked in DSA interviews, and the goal is to rearrange the elements so that after merging, the smallest len(arr1) elements remain in arr1 and the rest in arr2, all while preserving sorted order.

Problem Statement

Given two sorted arrays, arr1 and arr2, merge them in such a way that the combined sorted order is maintained without using any extra space. In other words, after merging, the first array should contain the first n smallest elements and the second array should contain the remaining elements.

Sample Input and Output

Example 1:

</>

Copy

# Input:
arr1 = [1, 3, 5, 7]
arr2 = [0, 2, 6, 8, 9]

# Output after merging:
arr1 = [0, 1, 2, 3]
arr2 = [5, 6, 7, 8, 9]

Example 2:

</>

Copy

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

# Output after merging:
arr1 = [5, 10]
arr2 = [12, 18, 20]

Solution Approach

One efficient way to merge two sorted arrays without extra space is by using the Gap Method. The approach works as follows:

Calculate the initial gap: Compute the gap as gap = ceil((n + m) / 2), where n and m are the lengths of arr1 and arr2 respectively.
Compare and swap elements:
- Compare elements within arr1 and swap if they are out of order.
- Compare elements between arr1 and arr2 and swap if needed.
- Compare elements within arr2 and swap if they are out of order.
Reduce the gap: Update the gap using the formula gap = ceil(gap / 2) until the gap becomes 0.
Result: After all iterations, the arrays will be merged and sorted in-place.

Python Program

</>

Copy

import math

def next_gap(gap):
    if gap <= 1:
        return 0
    return math.ceil(gap / 2)

def merge(arr1, arr2):
    n = len(arr1)
    m = len(arr2)
    gap = next_gap(n + m)
    
    while gap > 0:
        # Compare elements in arr1.
        i = 0
        while i + gap < n:
            if arr1[i] > arr1[i + gap]:
                arr1[i], arr1[i + gap] = arr1[i + gap], arr1[i]
            i += 1
        
        # Compare elements between arr1 and arr2.
        j = gap - n if gap > n else 0
        while i < n and j < m:
            if arr1[i] > arr2[j]:
                arr1[i], arr2[j] = arr2[j], arr1[i]
            i += 1
            j += 1
        
        # Compare elements in arr2.
        if j < m:
            j = 0
            while j + gap < m:
                if arr2[j] > arr2[j + gap]:
                    arr2[j], arr2[j + gap] = arr2[j + gap], arr2[j]
                j += 1
        
        gap = next_gap(gap)

# Example Usage:

# Example 1:
arr1 = [1, 3, 5, 7]
arr2 = [0, 2, 6, 8, 9]
merge(arr1, arr2)
print("Merged Arrays:")
print("arr1:", arr1)  # Expected Output: [0, 1, 2, 3]
print("arr2:", arr2)  # Expected Output: [5, 6, 7, 8, 9]

# Example 2:
arr1 = [10, 12]
arr2 = [5, 18, 20]
merge(arr1, arr2)
print("\nMerged Arrays:")
print("arr1:", arr1)  # Expected Output: [5, 10]
print("arr2:", arr2)  # Expected Output: [12, 18, 20]

Conclusion

The Gap Method is an efficient and elegant solution for merging two sorted arrays without using extra space. By progressively reducing the gap and swapping out-of-order elements, we can merge the arrays in-place while maintaining sorted order.

TutorialKart

Python – Merge Two Sorted Arrays Without Using Extra Space