Python exercise: merge two sorted feeds and preserve left-first ties

Operation contract

The fixture accepts two bounded nondecreasing integer feeds. It emits each amount with a source label, choosing the left feed first when values tie. Each input remains unchanged. The output therefore has a declared tie policy that can be tested separately from merely being sorted. A two-pointer scan avoids sorting the combined feed again.

Failure and ownership boundary

The function validates both order contracts before merging; a single out-of-order value is rejected rather than hidden by a later sort. For large live feeds, materializing both inputs and output would defeat streaming. Python merge sort: stable ordering without editing the input, Python CSV ingestion: cap bytes, rows and fields before publication and Python iterators: exhaustion and repeatable collection ownership show the next boundaries.

Working program

def merge_feeds(left, right):
    for feed in (left, right):
        if type(feed) is not list or len(feed) > 100 or any(type(value) is not int or not 0 <= value <= 1000 for value in feed) or any(a > b for a, b in zip(feed, feed[1:])):
            raise ValueError("sorted bounded integer feed")
    merged = []
    left_index = right_index = 0
    while left_index < len(left) or right_index < len(right):
        if right_index == len(right) or left_index < len(left) and left[left_index] <= right[right_index]:
            merged.append((left[left_index], "left"))
            left_index += 1
        else:
            merged.append((right[right_index], "right"))
            right_index += 1
    return merged

print(merge_feeds([10, 20, 20], [20, 30]))
try:
    merge_feeds([20, 10], [])
except ValueError:
    print("unsorted feed rejected")

Output

[(10, 'left'), (20, 'left'), (20, 'left'), (20, 'right'), (30, 'right')]
unsorted feed rejected

Costs and limits

Validation and merge take O(n+m) time; output retains O(n+m) labeled pairs. The 100-item cap controls this exercise. A stream merge would keep smaller memory but must define how and when input errors become visible.

Common Mistakes

• Do not silently sort a feed whose declared input contract was broken.
• Using less-than rather than less-than-or-equal changes equal-key tie order.

Connected lessons

Python merge sort: stable ordering without editing the input, Python CSV ingestion: cap bytes, rows and fields before publication, Python iterators: exhaustion and repeatable collection ownership.

Trace the next boundary

Python heapq.merge: combine sorted feeds without sorting every value again.