Merge Sorted Arrays

Given two arrays that are already sorted, the goal is to combine them into a single sorted array (or merge one into the other in place) without using extra sorting of the whole combined array.

Two-Pointer Approach

Maintain a pointer for each array. Compare the elements the pointers point to, push the smaller one into the result, and advance that pointer. Continue until one array is exhausted, then append the remainder of the other.

def merge_sorted_arrays(a, b):
    i = j = 0
    merged = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            merged.append(a[i]); i += 1
        else:
            merged.append(b[j]); j += 1
    merged.extend(a[i:])
    merged.extend(b[j:])
    return merged

In-Place Variant (LeetCode Style)

When array A has enough trailing empty space to hold array B's elements, merge from the back to avoid overwriting unprocessed values.

Complexity

Applications

• The merge step is the core building block of Merge Sort.
• Merging sorted result sets from distributed/parallel computations.
• Combining sorted log files or streams.