Merging Sorted Sequences

Merging two sorted sequences into one sorted result is one of the most fundamental operations in computer science. It underpins merge sort, powers database joins, and appears directly in a handful of classic interview problems. The good news: the core idea is dead simple. You look at the front of both sequences, take whichever element is smaller, and repeat until everything has been placed.

Let us start with the purest version of this idea: merging two sorted linked lists (LeetCode 21, Merge Two Sorted Lists).

The Two-Pointer Merge

You maintain one pointer into each list. At every step you compare the values at the two pointers, attach the smaller node to your result, and advance that pointer. When one list runs out, you append the entire remainder of the other list. It is already sorted, so there is nothing left to compare.

There is a small implementation wrinkle with linked lists: you need somewhere to attach the very first node of the result before you know what it will be. The standard trick is to create a dummy node, a throwaway node whose next pointer will eventually point to the real head of the merged list. You build the result by advancing a tail pointer that starts at the dummy. When you are done, dummy.next is your answer. This avoids an awkward special case where you would otherwise need an if head is None check on every iteration.

Walking Through Merge Two Sorted Lists

Suppose we are merging list A = [1, 2, 4] and list B = [1, 3, 4].

We start with both pointers at the head of their respective lists and an empty result built off a dummy node.

Compare A=1 and B=1. They are equal, so we take from A (either choice is fine). Result so far: [1]. A advances to 2.

Compare A=2 and B=1. B is smaller, so we take 1 from B. Result: [1, 1]. B advances to 3.

Compare A=2 and B=3. A is smaller, so we take 2. Result: [1, 1, 2]. A advances to 4.

Compare A=4 and B=3. B is smaller, so we take 3. Result: [1, 1, 2, 3]. B advances to 4.

Compare A=4 and B=4. They are equal, take from A. Result: [1, 1, 2, 3, 4]. A is now exhausted.

We append the rest of B, which is just [4]. Final merged list: [1, 1, 2, 3, 4, 4].

Every element is visited exactly once. Two pointers, one pass: that is the whole algorithm.

Code: Merge Two Sorted Lists

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_two_lists(l1, l2):
    dummy = tail = ListNode(0)
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

The line tail.next = l1 or l2 handles the cleanup: whichever list still has nodes gets appended in one shot. Time is $O(n + m)$ where n and m are the list lengths. Space is $O(1)$ because we are rewiring existing nodes, not creating new ones.

Merge Sorted Array: The Backwards Fill Trick

LeetCode 88 (Merge Sorted Array) gives you a twist. You have two sorted arrays, nums1 and nums2. The first array has enough trailing zeros to hold both arrays' elements. You need to merge them in-place into nums1.

The naive approach, merging from the front, immediately runs into trouble. If nums2 has a small element, you would need to insert it at the beginning of nums1, shifting everything to the right. That is $O(n)$ per insertion and $O(n \cdot m)$ overall.

The insight is to fill from the back. The trailing zeros in nums1 are at the end, so the end of the array is free real estate. Start three pointers: p1 at the last real element of nums1 (index m - 1), p2 at the last element of nums2 (index n - 1), and write at the very last position of nums1 (index m + n - 1). Compare the elements at p1 and p2, place the larger one at the write position, and decrement the appropriate pointers. You are filling the array from right to left with the largest remaining elements.

Why does this work without overwriting anything you still need? At every step, the write pointer is at position p1 + p2 + 1 or further right. Since write >= p1 always holds, you never clobber an unprocessed element in nums1. The trailing zeros act as a buffer that absorbs each placement, and that buffer is always large enough because it was sized to hold exactly n extra elements.

Walking Through Merge Sorted Array

Take nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3.

We initialize p1 = 2 (pointing at value 3), p2 = 2 (pointing at value 6), and write = 5.

Compare nums1[p1]=3 and nums2[p2]=6. Place 6 at index 5, decrement p2 and write. Array becomes [1, 2, 3, 0, 0, 6].

Compare nums1[p1]=3 and nums2[p2]=5. Place 5 at index 4. Array: [1, 2, 3, 0, 5, 6].

Compare nums1[p1]=3 and nums2[p2]=2. Place 3 at index 3, decrement p1. Array: [1, 2, 3, 3, 5, 6].

Compare nums1[p1]=2 and nums2[p2]=2. They are equal; take from nums1. Place 2 at index 2, decrement p1. Array: [1, 2, 2, 3, 5, 6].

Compare nums1[p1]=1 and nums2[p2]=2. Place 2 at index 1, decrement p2. Array: [1, 2, 2, 3, 5, 6].

p2 is now -1, so the loop ends. The remaining elements in nums1 (just the 1 at index 0) are already in their correct positions. Done.

Code: Merge Sorted Array

def merge(nums1, m, nums2, n):
    p1, p2, write = m - 1, n - 1, m + n - 1
    while p2 >= 0:
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[write] = nums1[p1]
            p1 -= 1
        else:
            nums1[write] = nums2[p2]
            p2 -= 1
        write -= 1

Notice the loop condition is while p2 >= 0. Once all of nums2 has been placed, the remaining elements in nums1 are already sorted and in the correct positions. There is nothing left to do. Time is $O(n + m)$ and space is $O(1)$.

Connection to Merge Sort

If the merge operation feels like a building block, that is because it literally is one. Merge sort works by recursively splitting an array in half, sorting each half, and then merging the two sorted halves back together. The merge step is exactly the two-pointer algorithm we have been discussing.

This is why merge sort runs in $O(n \log n)$ time. There are $O(\log n)$ levels of recursion, and each level splits the array in half. At each level, the total work across all merges is $O(n)$, because every element participates in exactly one merge at that level. Multiply $O(n)$ work per level by $O(\log n)$ levels and you get $O(n \log n)$.

Understanding the merge operation deeply means you already understand the heart of merge sort. And because merge sort processes elements sequentially rather than jumping around the array, it is also the algorithm of choice when you need a stable sort or when your data lives on disk and you want to minimize random access.

Merge K Sorted Lists: Scaling Up

LeetCode 23 scales this up: you are given k sorted lists instead of two. You could merge them one pair at a time: merge list 1 and list 2, then merge the result with list 3, and so on. But this approach is inefficient. If each list has roughly $n/k$ elements and there are k lists totaling N elements, the sequential approach processes increasingly large intermediate results, leading to $O(N \cdot k)$ total work.

The better approach uses a min-heap (priority queue) of size k. Push the head node of each list into the heap. Then repeatedly pop the smallest element, add it to the result, and push that element's successor into the heap (if it exists). The heap always contains at most k elements, one from each list, so each push and pop costs $O(\log k)$. Since you process every element exactly once across all lists, the total time is $O(N \log k)$, where N is the total number of elements.

Code: Merge K Sorted Lists

import heapq

def merge_k_lists(lists):
    dummy = tail = ListNode(0)
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

The i in each heap entry serves as a tiebreaker. Python's heapq compares tuples element by element, and if two nodes have the same value, it would try to compare the ListNode objects directly, which would raise an error. The index i breaks ties before that comparison is ever attempted.

Complexity Analysis

Merge Two Sorted Lists / Arrays: $O(n + m)$ time, where n and m are the sizes of the two inputs. Space is $O(1)$ for linked lists (rewiring pointers) and $O(1)$ for the backwards-fill array variant (in-place).

Merge K Sorted Lists: $O(N \log k)$ time, where N is the total number of elements across all k lists and k is the number of lists. Space is $O(k)$ for the heap.

The merge operation is one of those rare algorithms that is both simple and optimal. You cannot do better than $O(n + m)$ for merging two sorted sequences, because you must examine every element at least once. When you see a problem involving sorted sequences that need to be combined, the two-pointer merge should be the first tool you reach for.

Recognizing this pattern

You're probably looking at merging sorted sequences when:

• The inputs are already sorted (or trivially sortable) and you need a combined, sorted output.
• You're asked to merge into one of the inputs in-place, usually requiring you to write from the back.
• The problem reduces to "take the smaller of two heads" at each step.
• More than two sequences are involved and you want $O(N \log k)$ via a heap rather than repeated pairwise merges.

Common templates:

• Two-pointer merge (out-of-place): walk both inputs forward, append the smaller, dump the remainder. Example: Merge Two Sorted Lists.
• Merge in-place from the back: when one array has trailing space, write from the rightmost slot to avoid overwriting unread values. Example: Merge Sorted Array.
• K-way merge with a min-heap: push the heads of all k sequences; pop, append, advance, push next. Example: Merge k Sorted Lists.
• Merge as a subroutine for inversions or order stats: piggy-back on merge sort to count cross-boundary contributions. Example: Count of Smaller Numbers After Self.