Merging Two Sorted Arrays

Keep one pointer in each array and one pointer in the output. At each step, compare the values the two input pointers point at, copy the smaller one into the output, and advance that pointer. When one array is exhausted, append whatever remains of the other.

def merge_sorted(a, b):
    merged = []
    i = j = 0
    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

print(merge_sorted([1, 3, 5], [2, 4, 6]))
print(merge_sorted([1, 2], []))

The outputs are 1, 2, 3, 4, 5, 6 and 1, 2. The second call shows the empty-array case, where the loop never runs and the first array is appended unchanged.

The reason the merge is linear is that neither input is ever rescanned. Each element is compared once and copied once, so the total work is proportional to the combined length. That is the property that makes merge sort efficient: the merge step is O of n, and it is applied at every level of a logarithmic recursion tree, giving O of n log n overall.

The trade-off to name is space. This version allocates a third list, so it uses O of n extra memory and leaves both inputs untouched. That is usually the right choice, because keeping the inputs intact avoids aliasing bugs. The in-place variant, where the result overwrites one of the inputs, saves the extra array but requires the destination to have enough room and is noticeably more intricate to get right. As with any merge, using less-than-or-equal in the comparison keeps the sort stable, which matters when equal elements carry different payloads.

The trick is to fill the destination from the back. The first array is expected to have spare slots at the end, and you merge backwards so that no unread value is ever overwritten. Place a pointer at the last position of the combined length and work backwards, comparing the last unused element of each source array and writing the larger one into the destination.

def merge_into_first(a, b, m):
    n = len(b)
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and a[i] > b[j]:
            a[k] = a[i]; i -= 1
        else:
            a[k] = b[j]; j -= 1
        k -= 1
    return a

first = [1, 3, 5, 0, 0, 0]
print(merge_into_first(first, [2, 4, 6], 3))

The output is 1, 2, 3, 4, 5, 6. The first array had three real values followed by three placeholder zeros, and the merge filled those three slots with the three values from the second array, sorted into place.

The reason it has to run backwards is overwriting. If you merged forwards into the first array, writing a merged value into position zero would destroy a value you have not read yet, because the merged output grows faster than the input pointers advance. Filling from the back avoids that entirely: every write goes to a position at or beyond both read pointers, so no unread element is ever clobbered.

The trade-off to name is that this only works when the destination has spare capacity. The count of real values has to be passed in separately, because the caller knows how many leading entries of the first array are meaningful and the rest are placeholders. The forward version needs no such guarantee but allocates a new list. In practice the library function sorted, or the merge from the previous answer, is the better call; this version is worth knowing because it appears in interview questions that explicitly forbid extra arrays, and because the backwards-filling idea generalises to merging three arrays and to the classic merge of two sorted linked lists.