Practice: Merging Two Sorted Departure Boards

Two platforms each list departures in time order; produce one board in time order.

Merging two sorted lists is merge sort's merge step used on its own, and this exercise practises it: combining two lists that are each already in order into one list in order, keeping the first list's item first on a tie. The merge turns up well beyond sorting, wherever two ordered feeds meet.

A small station has two platforms, and each prints its own departure board in time order:

Platform A: 08:05, 08:20, 08:40.
Platform B: 08:10, 08:20, 08:55.

The station wants one board listing all six trains in time order. When two trains leave at the same minute, platform A's train is listed first. Write out the combined board, with each train's platform, and say how many comparisons the merge makes. Then write a function that merges two boards given as lists of (time, platform) pairs. Times written as two-digit hours and minutes compare correctly as strings, so "08:10" < "08:20" holds.

Show the answer

The board is 08:05 A, 08:10 B, 08:20 A, 08:20 B, 08:40 A, 08:55 B, after 5 comparisons. Platform A's list plays the left half and platform B's the right, and the tie at 08:20 goes to platform A because the comparison is <=. The trace shows both boards side by side, with a and b on the next train from each.

Merging two departure boards, one frame per train placed

Inputplatform A in cells 0 to 2, platform B in cells 3 to 5

Start
1. 08:05a
2. 08:20
3. 08:40
4. 08:10b
5. 08:20
6. 08:55
Platform A's times sit in cells 0 to 2 and platform B's in cells 3 to 5. a and b point at the first departure on each.
Take 08:05 A
1. 08:05
2. 08:20a
3. 08:40
4. 08:10b
5. 08:20
6. 08:55
08:05 is earlier than 08:10, so platform A's train goes on the board first and a moves on.
Take 08:10 B
1. 08:05
2. 08:20a
3. 08:40
4. 08:10
5. 08:20b
6. 08:55
08:10 is earlier than 08:20, so platform B's train comes next and b moves on.
Take 08:20 A
1. 08:05
2. 08:20
3. 08:40a
4. 08:10
5. 08:20b
6. 08:55
Both fronts read 08:20. The comparison is <=, so the tie goes to platform A, the left list, and a moves on.
Take 08:20 B
1. 08:05
2. 08:20
3. 08:40a
4. 08:10
5. 08:20
6. 08:55b
08:20 on platform B is now earlier than 08:40, so it goes next.
Take 08:40 A
1. 08:05
2. 08:20
3. 08:40
4. 08:10
5. 08:20
6. 08:55b
08:40 is earlier than 08:55. It was platform A's last departure, so a has nothing left to point at.
Copy the rest
1. 08:05
2. 08:20
3. 08:40
4. 08:10
5. 08:20
6. 08:55
Platform A is empty, so 08:55 from platform B goes on the end with no comparison.

Result08:05 A, 08:10 B, 08:20 A, 08:20 B, 08:40 A, 08:55 B

Each of the first five trains placed cost one comparison. After 08:40, platform A had nothing left, so 08:55 went on the end without one. A function that does the same takes the front of each list, keeps the earlier time, and copies the remainder when one list runs out.

departure_boards.pypy

platform_a = ["08:05", "08:20", "08:40"]
platform_b = ["08:10", "08:20", "08:55"]


def merge_boards(first, second):
    board, i, j = [], 0, 0
    while i < len(first) and j < len(second):
        if first[i][0] <= second[j][0]:
            board.append(first[i])
            i += 1
        else:
            board.append(second[j])
            j += 1
    return board + first[i:] + second[j:]


board = merge_boards([(time, "A") for time in platform_a], [(time, "B") for time in platform_b])
for time, platform in board:
    print(time, platform)

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

08:05 A
08:10 B
08:20 A
08:20 B
08:40 A
08:55 B

Line 8 is the tie rule: <= on the times sends a tie to first, which is platform A. With <, 08:20 B would print before 08:20 A, a board that is still in time order but breaks the station's rule. The last line of the function copies whatever remains of either list; leave it out and the 08:55 train disappears from the board. Pass the boards in the other order and platform B wins every tie, so the order the boards are passed in decides every tie.

← → move through sections and cards