Merge Sorted Arrays

The Problem

Given two sorted integer arrays arr1 and arr2, merge them into a single sorted array and return it.

arr1 = [1, 3, 5, 7],  arr2 = [2, 4, 6]      →  [1, 2, 3, 4, 5, 6, 7]
arr1 = [1, 2, 3],     arr2 = []              →  [1, 2, 3]
arr1 = [],             arr2 = [1, 2]          →  [1, 2]
arr1 = [1, 3],         arr2 = [2, 4]          →  [1, 2, 3, 4]

Examples

Example 1

Input:  arr1 = [1, 3, 5, 7],  arr2 = [2, 4, 6]
Output: [1, 2, 3, 4, 5, 6, 7]

Example 2

Input:  arr1 = [1, 5, 9],  arr2 = [2, 3, 7, 10]
Output: [1, 2, 3, 5, 7, 9, 10]

Example 3

Input:  arr1 = [1, 2, 3],  arr2 = []
Output: [1, 2, 3]

Both arrays are already sorted. Think of them as two sorted piles of cards face-up in front of you. You want to produce one big sorted pile by repeatedly taking the smaller of the two top cards. At any point you only need to look at the top of each pile — never deeper.

This is a textbook simultaneous traversal problem:

You need both arrays processed together — you can’t finish one and then start the other, because elements from both interleave in the result.
At each step, a comparison between the two current elements decides which index advances.
The advance condition is simple and deterministic: take the smaller element.

After one pile is exhausted, the remaining cards in the other pile are already in sorted order — just append them all directly.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Init(["i = 0, j = 0, result = []"])
  Check{"i < len(arr1)<br/>AND j < len(arr2)?"}
  Cmp{"arr1[i] <= arr2[j]?"}
  TakeL["result.append(arr1[i])<br/>i += 1"]
  TakeR["result.append(arr2[j])<br/>j += 1"]
  DrainL["append remaining arr1[i:]<br/>i advances to end"]
  DrainR["append remaining arr2[j:]<br/>j advances to end"]
  Done(["return result"])

  Init --> Check
  Check -->|"yes"| Cmp
  Cmp -->|"yes — arr1 smaller"| TakeL --> Check
  Cmp -->|"no — arr2 smaller"| TakeR --> Check
  Check -->|"no — one array exhausted"| DrainL
  DrainL --> DrainR --> Done

Merge Sorted Arrays — compare the front elements of each array, take the smaller, advance that pointer. Drain whichever array remains after the main loop.

Brute Force: Concatenate and Sort, O((N+M) log(N+M))

The naive approach ignores the fact that both arrays are already sorted:

from typing import List

def merge_sorted_brute(arr1: List[int], arr2: List[int]) -> List[int]:
    # Concatenate both arrays and sort the combined result
    combined = arr1 + arr2
    # Sort discards the pre-sorted structure — wasted work
    combined.sort()
    return combined

print(merge_sorted_brute([1, 3, 5, 7], [2, 4, 6]))  # [1, 2, 3, 4, 5, 6, 7]

This works but is wasteful — it throws away the sorted structure both arrays already have. The sort does O((N+M) log(N+M)) work when O(N+M) is achievable.

Solution

from typing import List

class Solution:
    def merge_sorted_arrays(self, arr1: List[int], arr2: List[int]) -> List[int]:
        result = []
        # Initialize pointers at the start of each array
        i = 0
        j = 0

        # Main loop: run while both arrays have unprocessed elements
        while i < len(arr1) and j < len(arr2):
            if arr1[i] <= arr2[j]:
                # arr1's front element is smaller or equal — take it
                result.append(arr1[i])
                i += 1
            else:
                # arr2's front element is smaller — take it
                result.append(arr2[j])
                j += 1

        # Drain any remaining elements in arr1
        while i < len(arr1):
            result.append(arr1[i])
            i += 1

        # Drain any remaining elements in arr2
        while j < len(arr2):
            result.append(arr2[j])
            j += 1

        return result


sol = Solution()
print(sol.merge_sorted_arrays([1, 3, 5, 7], [2, 4, 6]))       # [1, 2, 3, 4, 5, 6, 7]
print(sol.merge_sorted_arrays([1, 5, 9], [2, 3, 7, 10]))       # [1, 2, 3, 5, 7, 9, 10]
print(sol.merge_sorted_arrays([1, 2, 3], []))                  # [1, 2, 3]
print(sol.merge_sorted_arrays([], [1, 2]))                     # [1, 2]
print(sol.merge_sorted_arrays([1, 1, 2], [1, 3]))              # [1, 1, 1, 2, 3]

Dry Run — Example 1

arr1 = [1, 3, 5, 7], arr2 = [2, 4, 6]

Trace — arr1 = [1, 3, 5, 7], arr2 = [2, 4, 6]

i=0, j=0, result=[]

Step 1 │ arr1[0]=1, arr2[0]=2 │ 1 ≤ 2 → take arr1[0]=1 │ result=[1],     i=1, j=0
Step 2 │ arr1[1]=3, arr2[0]=2 │ 3 > 2 → take arr2[0]=2 │ result=[1,2],   i=1, j=1
Step 3 │ arr1[1]=3, arr2[1]=4 │ 3 ≤ 4 → take arr1[1]=3 │ result=[1,2,3], i=2, j=1
Step 4 │ arr1[2]=5, arr2[1]=4 │ 5 > 4 → take arr2[1]=4 │ result=[1,2,3,4], i=2, j=2
Step 5 │ arr1[2]=5, arr2[2]=6 │ 5 ≤ 6 → take arr1[2]=5 │ result=[1,2,3,4,5], i=3, j=2
Step 6 │ arr1[3]=7, arr2[2]=6 │ 7 > 6 → take arr2[2]=6 │ result=[1,2,3,4,5,6], i=3, j=3

j=3 == len(arr2)=3 → main loop exits

Drain arr1: arr1[3]=7 → result=[1,2,3,4,5,6,7], i=4
i=4 == len(arr1)=4 → drain loop exits

Result: [1, 2, 3, 4, 5, 6, 7] ✓

Both arrays contributed elements; the drain loop handled arr1's last element
because arr2 ran out one step before arr1 did.

Why the Cleanup Loops Are Essential

When the main loop exits, exactly one array is exhausted. The other array still has elements remaining — and they’re all guaranteed to be ≥ every element already in result (because both arrays are sorted and we always took the smaller element).

So we don’t need to compare any more — just append the remainder directly.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  A["Main loop exits<br/>one array exhausted"]
  B{"Which array<br/>still has elements?"}
  C["Append remaining arr1[i:]<br/>all ≥ last element in result"]
  D["Append remaining arr2[j:]<br/>all ≥ last element in result"]
  E["Result is fully sorted"]

  A --> B
  B -->|"arr2 exhausted"| C --> E
  B -->|"arr1 exhausted"| D --> E

After the main loop, all remaining elements in the surviving array are guaranteed to be ≥ every element already in the result — a direct append completes the merge.

Complexity Analysis

	Complexity	Reasoning
Time	O(N + M)	Every element in both arrays is processed exactly once — added to result and never revisited
Space	O(N + M)	The result array holds all N + M elements

Compare with brute force O((N+M) log(N+M)) — the simultaneous traversal saves the sort by exploiting the pre-sorted structure.

Edge Cases

Scenario	Input	Output	Note
One array empty	`arr1=[]`, `arr2=[1,2]`	`[1, 2]`	Main loop never runs; drain arr2 copies everything
Both empty	`arr1=[]`, `arr2=[]`	`[]`	No loop runs; return empty result
Arrays with duplicates	`[1,1,2]`, `[1,3]`	`[1,1,1,2,3]`	Duplicates handled naturally — `<=` takes from arr1 on tie
arr1 entirely smaller	`[1,2,3]`, `[4,5,6]`	`[1,2,3,4,5,6]`	Main loop takes all of arr1 first, then drain copies arr2
arr2 entirely smaller	`[4,5,6]`, `[1,2,3]`	`[1,2,3,4,5,6]`	Main loop takes all of arr2 first, then drain copies arr1

Key Takeaway

Merge Sorted Arrays is the canonical simultaneous traversal problem. The key insight: both arrays are already sorted, so at every step the smallest unseen element is always one of the two front elements. A single comparison picks it, one pointer advances, and the sorted invariant is maintained throughout. The cleanup loops are not optional — they handle the common case where one array runs out before the other.

Note Book