One shelving run

Two return chutes, each already in shelf order, and one shelver who walks the stacks once. The books have to become a single rail before the doors open.

The problem

A library has two overnight return chutes. As books drop in, a clerk hangs each one on that chute's trolley rail, so by morning there are two rails, each reading in non-decreasing shelf number front to back.

The shelver walks the stacks in one direction only, so both rails have to become one rail, still in non-decreasing shelf number. Books cannot be laid out on a table — there is no table. The only move allowed is unhooking a book from the front of a rail and hooking it onto the back of the run being built. Two copies of the same title carry the same shelf number, and both must appear in the run.

Input. chute_a, chute_b — two lists of integers, the shelf numbers on each rail, each already in non-decreasing order. Either may be empty.

Output. One list of shelf numbers in non-decreasing order, holding every book from both rails.

Example.

chute_a = [104, 210, 377], chute_b = [96, 211, 240, 512]  ->  [96, 104, 210, 211, 240, 377, 512]

96 goes first, then 104 and 210, then 211 and 240, then 377 — and 512 is left alone at the end, when the first rail has run dry.

A second example, on the two cases that break careless code:

chute_a = [], chute_b = [301, 301]  ->  [301, 301]
chute_a = [7, 7, 7], chute_b = [7, 7]  ->  [7, 7, 7, 7, 7]

An empty chute contributes nothing and must not be read. Five books all bound for shelf 7 must all still be on the rail at the end.

Constraints.

• 0 <= len(chute_a), len(chute_b) <= 5 * 10^4
• 1 <= shelf number <= 10^6
• both inputs are already non-decreasing
• Extra memory O(1) beyond the run being built: no copy of either chute.

Hints

Approach

Brute force

Tip both rails into one pile and sort it: (n + m) log(n + m) comparisons, about 1.7 million at 100,000 books, plus a full copy of both chutes. It works, and it throws away the order each chute already had.

The insight

Both rails are sorted, so the smallest book not yet hung is always the front book of one rail or the other, and a single comparison decides each step.

That drops the work to n + m comparisons, one per book hung. The precondition is the order each chute already has: if one rail arrived out of order the front-of-rail rule is false and the output is wrong, not merely slow — which is also why the same loop is the merge step of a merge sort.

A dummy hook at the front of the run removes the other special case. Without it, the first book needs "is the run empty?" inside the loop; with it, every hang is tail.next = book; tail = book, and the answer is whatever the dummy ends up pointing at.

Algorithm

1. Make a dummy hook; set tail to it.
2. While both rails still have a front book, compare the two shelf numbers.
3. Hang the smaller one, advance that rail, advance tail.
4. When the loop ends, hook the remaining rail on whole: tail.next is whichever of the two is not empty.
5. Return dummy.next.

Complexity

Time O(n + m) — every book is compared at most once and hung exactly once. Space O(1) — the dummy, two rail references and a tail, whatever the size of the chutes.

Solution

"""One shelving run — merge two ordered chains behind a dummy hook."""


class Book:
    """One book on a trolley rail; `nxt` is the book behind it."""

    def __init__(self, shelf, nxt=None):
        self.shelf = shelf
        self.nxt = nxt


def hang(shelves):
    """Build a rail from a list of shelf numbers and return its front book."""
    front = None
    for shelf in reversed(shelves):
        front = Book(shelf, front)
    return front


def read_rail(front):
    """Walk the run and write out the shelf numbers in order."""
    shelves = []
    while front:
        shelves.append(front.shelf)
        front = front.nxt
    return shelves


def solve(chute_a, chute_b):
    a, b = hang(chute_a), hang(chute_b)

    dummy = Book(0)     # thrown away: it exists so no hang is a special case
    tail = dummy
    while a and b:
        # invariant: the smallest book not yet hung is at the front of a or of b,
        # because each rail is already in non-decreasing order.
        if a.shelf <= b.shelf:
            tail.nxt = a
            a = a.nxt
        else:
            tail.nxt = b
            b = b.nxt
        tail = tail.nxt
    tail.nxt = a or b   # the rest of the surviving rail is already in order

    return read_rail(dummy.nxt)

TESTS = [
    (([104, 210, 377], [96, 211, 240, 512]), [96, 104, 210, 211, 240, 377, 512]),
    (([], [301, 301]), [301, 301]),
    (([7, 7, 7], [7, 7]), [7, 7, 7, 7, 7]),
    (([], []), []),
    (([1000000], []), [1000000]),
    (([1, 2, 3], [90, 91]), [1, 2, 3, 90, 91]),
    (([90, 91], [1, 2, 3]), [1, 2, 3, 90, 91]),
]

Pitfalls

• Forgetting the leftover rail. The loop stops when either chute empties, and everything still hanging on the other is silently dropped. The first example comes back as [96, 104, 210, 211, 240, 377] — 512 never shelved.
• Returning the dummy. The caller gets the throwaway hook's number at the front of the run — a phantom book at shelf 0. Return dummy.next.
• Advancing both rails when the numbers are equal. It looks like it saves a step and it loses a book each time: [7, 7, 7] and [7, 7] come back as four books, not five. On a tie, hang one and advance one.

Variants

• Trimming the playout — the same dummy hook, used to delete a node rather than to build a chain.
• Pointer surgery — why the dummy removes the first-element branch everywhere it appears.