Skip to content
MINH VO A working notebook
by an engineer in Vietnam
Foundation8 min read

Two pointers for merging sorted attendance lists

Merge sorted attendance records with two pointers while preserving duplicates and stable ties, then prove linear work and distinguish a merge from set union.

Pencil-drawn graph on beige paper, with olive paths connecting its nodes

Merging two sorted lists takes one pass through each list because their smallest remaining elements are always at the two current positions. For a student learning two-pointer algorithms, attendance IDs make a useful example, provided the result’s duplicate policy is explicit. This version preserves every input record, including repeated IDs.

Suppose one session exports [2, 4, 4, 9] and another exports [1, 4, 7]. A sorted merge returns [1, 2, 4, 4, 4, 7, 9]. It does not claim there were seven different people. The duplicate fours may represent separate events, duplicate exports, or records needing later cleanup. Deciding what duplicates mean is a different operation from arranging all the records in order.

Consume exactly one next record

Keep index i into the left list and index j into the right list. Compare the next unconsumed values and append the smaller one. When they are equal, choose the left value first. Increment only the pointer belonging to the value you appended.

def merge_sorted(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result

assert merge_sorted([2, 4, 4, 9], [1, 4, 7]) == [1, 2, 4, 4, 4, 7, 9]
assert merge_sorted([], [1, 1]) == [1, 1]
assert merge_sorted([], []) == []

The tail loops begin only after one side is exhausted. All remaining values on the other side are already sorted, so they can be appended without further cross-list comparisons. The implementation leaves both source lists unchanged and allocates a new result.

In the running example, one beats two, then two beats four. The next comparison is four against four, so the first left four is appended. The second left four also wins its tie. Right four and right seven follow, and the final left nine is copied by the tail loop.

Merge trace for left IDs two, four, four, nine and right IDs one, four, seven; the output preserves three fours and labels each value by its sourceView full-size image ↗

The diagram marks the source of each output record. Equal values from the left appear before equal values from the right, and each source retains its original order. This is the stable tie rule used by the example.

A sorted prefix is the invariant

Before each main-loop iteration, the result contains exactly the consumed prefixes of the two inputs, in sorted order. Every value still waiting is at least as large as the last output value. Initially the output and both consumed prefixes are empty, so these conditions hold.

Because each input is sorted, its first unconsumed value is the smallest remaining value from that input. The smaller of those two candidates is therefore the smallest value remaining anywhere. Appending it preserves order and adds exactly one record to the consumed prefixes. The selected pointer advances, so no input occurrence can be appended twice.

When one list runs out, all its occurrences have already been accounted for. The other list’s remaining suffix belongs after the output prefix and can be copied directly. The final result therefore has length len(left) + len(right), contains every input occurrence, and is sorted.

This argument is the merge step underlying merge sort. Princeton’s mergesort discussion explains how repeatedly merging sorted subarrays gives a complete sorting algorithm. Here the sorted inputs are part of the caller’s contract, so the cost of producing them is outside this operation.

Count advances before measuring time

If the lengths are m and n, pointer i advances m times and pointer j advances n times. Each append consumes one occurrence. Total runtime is Θ(m + n) under constant-cost comparison and amortized constant-time append.

When both inputs are nonempty, the main loop performs at most m + n - 1 cross-list comparisons. At that point at least one list must be exhausted, leaving a final element for the tail. Some inputs use fewer comparisons, such as when every left value is smaller than the first right value.

The returned list stores m + n references, so output space is Θ(m + n). The pointers themselves use O(1) auxiliary space. If a consumer can process one record at a time, a generator can yield the merge instead of storing the full output. Python’s heapq.merge provides a lazy merge for already sorted inputs and can handle more than two streams.

Merge records without materializing the output

A record’s sort key and its identity are different. To make stability observable, give equal IDs distinct labels and compare only the ID. The following generator also changes the output contract: it yields records as the caller requests them, instead of building a result list immediately.

def merge_records(left, right, key):
    left_iter, right_iter = iter(left), iter(right)
    missing = object()
    a = next(left_iter, missing)
    b = next(right_iter, missing)
    while a is not missing and b is not missing:
        if key(a) <= key(b):
            yield a
            a = next(left_iter, missing)
        else:
            yield b
            b = next(right_iter, missing)
    while a is not missing:
        yield a
        a = next(left_iter, missing)
    while b is not missing:
        yield b
        b = next(right_iter, missing)

seen = []
def observed(source, records):
    for record in records:
        seen.append((source, record[1]))
        yield record

left = [(4, 'L1'), (4, 'L2'), (9, 'L3')]
right = [(4, 'R1'), (7, 'R2')]
merged = merge_records(observed('left', left), observed('right', right),
                       key=lambda record: record[0])
assert seen == []
first = next(merged)
assert first == (4, 'L1')
assert seen == [('left', 'L1'), ('right', 'R1')]
assert [first, *merged] == [
    (4, 'L1'), (4, 'L2'), (4, 'R1'), (7, 'R2'), (9, 'L3'),
]

The first request from a lazy record merge reads only L1 and R1, both with ID four, yields L1 by the left-first tie rule, and leaves L2 L3 and R2 unreadView full-size image ↗

As Python’s yield-expression reference explains, constructing the generator does not begin its body. The first request reads one record from each input so it can compare their keys, then yields L1. Its left iterator advances again only when execution resumes after that yield. The source labels in seen make those reads observable without relying on a timing measurement. Both inputs must provide their next candidate before the merge can safely choose between them.

The private sentinel represents exhaustion. Using a private object avoids confusing an exhausted input with a legitimate record whose value happens to be None; such a record is acceptable only if the supplied key function knows how to order it. This example’s actual records are ID-label tuples, and its key function expects that format.

The generator keeps constant lookahead state for two inputs and yields each occurrence once. That does not bound memory already owned by the input iterators or retained by the caller. Converting the generator into a list still allocates storage proportional to the total output. Key extraction is part of the comparison cost; if computing a key is expensive, cache the key for the currently held record instead of repeatedly deriving it.

The stable equality choice keeps L1 and L2 ahead of R1, while each input’s own order stays intact. Sorting full tuples would instead introduce the labels into the ordering, which would be a different contract. The example assumes finite sorted inputs with a consistent key ordering; the merge does not sort, deduplicate or validate the producers as it goes.

Try taking only the first output and inspecting the read log, then exhausting the generator. Repeat with an empty side and with equal IDs whose labels would sort in the opposite order. A test that looks only at the numeric IDs cannot expose an incorrect tie policy, and a test that always converts everything to a list cannot demonstrate lazy consumption.

Change the contract deliberately

A set union would remove repeated IDs. An intersection would keep only IDs found in both inputs, with another decision about multiplicity. Those functions can also use two pointers, but their equality branches and output counts differ. Reusing this merge while assuming it deduplicates attendance would produce an incorrect business result.

Unsorted input breaks the proof immediately. Merging [4, 2] with [1, 3] can produce [1, 3, 4, 2], because the two-pointer method never searches behind a current position for a smaller value. You can validate sortedness in a linear pass, or make the producer responsible for the guarantee. For records, compare the same key and direction used by both producers.

Tests should include empty sides, one side entirely before the other, alternating values, and repeated values spanning both sides. To test stable behavior, attach source labels and compare only the numeric key; equal bare integers cannot reveal whether their original order was preserved. Also check input lists after the call if immutability is part of the public contract.

Sources & further reading

  1. Python documentation, heapq.merge
  2. Princeton Algorithms, Mergesort
  3. Python language reference, Yield expressions
← Back to the journal
All notes

Illustration

100%