As-of join of trades and quotes

You have two time-sorted streams: trades (ts, price) and quotes (ts, mid). For every trade, find the prevailing quote, the latest quote with quote_ts <= trade_ts. This "as-of join" is the primitive behind slippage analysis, markout curves, and effective-spread computation (kdb+'s aj, pandas' merge_asof).

quotes = [(1, 100.0), (3, 101.0), (7, 103.0)]
trades = [(2, 100.1), (3, 100.9), (5, 101.2)]
->
[(2, 100.1, 100.0),     # last quote at ts<=2 is the ts=1 quote
 (3, 100.9, 101.0),     # ties: quote at ts=3 counts (at-or-before)
 (5, 101.2, 101.0)]

Implement the join in $O(n + m)$, one pass over each stream. Binary-searching the quote list per trade is $O(n \log m)$, fine for one-offs, but the linear merge is the expected answer for sorted inputs.