# Array Merge

# Array Merge

Array merge combines two sorted arrays into one sorted sequence. It is a fundamental operation in merge sort and external sorting.

You use it when two ordered sequences must be combined while preserving order.

## Problem

Given two sorted arrays $A$ and $B$ of lengths $n$ and $m$, produce a sorted array $C$ containing all elements:

$$
C = \text{merge}(A, B)
$$

## Algorithm

Use two pointers and repeatedly select the smaller element.

```id="array-merge"
merge(A, B):
    i = 0
    j = 0
    C = empty array

    while i < length(A) and j < length(B):
        if A[i] <= B[j]:
            append A[i] to C
            i += 1
        else:
            append B[j] to C
            j += 1

    while i < length(A):
        append A[i] to C
        i += 1

    while j < length(B):
        append B[j] to C
        j += 1

    return C
```

## Example

Let

$$
A = [1, 4, 7]
$$

and

$$
B = [2, 3, 6]
$$

| step |  i |  j | chosen | C                  |
| ---- | -: | -: | ------ | ------------------ |
| 1    |  0 |  0 | 1      | [1]                |
| 2    |  1 |  0 | 2      | [1, 2]             |
| 3    |  1 |  1 | 3      | [1, 2, 3]          |
| 4    |  1 |  2 | 4      | [1, 2, 3, 4]       |
| 5    |  2 |  2 | 6      | [1, 2, 3, 4, 6]    |
| 6    |  2 |  3 | 7      | [1, 2, 3, 4, 6, 7] |

Result:

$$
[1, 2, 3, 4, 6, 7]
$$

## Correctness

At each step, the algorithm selects the smallest remaining element from the heads of $A$ and $B$. Since both arrays are sorted, this element is the smallest among all remaining elements. Appending it preserves sorted order.

After one array is exhausted, the remaining elements of the other array are already in sorted order and can be appended directly.

## Complexity

| operation | time       |
| --------- | ---------- |
| merge     | $O(n + m)$ |

Space usage:

$$
O(n + m)
$$

## When to Use

Array merge is appropriate when:

* combining sorted sequences
* implementing merge sort
* merging results from multiple sources
* streaming sorted data

It is less suitable when:

* inputs are unsorted
* in-place merging is required with strict memory constraints

## Implementation

```python id="array-merge-python"
def merge(a, b):
    i, j = 0, 0
    c = []

    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1

    c.extend(a[i:])
    c.extend(b[j:])
    return c
```

```go id="array-merge-go"
func Merge(a, b []int) []int {
    i, j := 0, 0
    c := make([]int, 0, len(a)+len(b))

    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            c = append(c, a[i])
            i++
        } else {
            c = append(c, b[j])
            j++
        }
    }

    c = append(c, a[i:]...)
    c = append(c, b[j:]...)
    return c
}
```