Sort-merge inner join
Your task
Implement a sort-merge inner join on two tables already sorted by their join key. Each table is a list of [key, value] pairs sorted ascending by key (keys are ints, duplicates allowed within a table). Produce all matching pairs [left_value, right_value] for rows where left.key == right.key, handling the many-to-many case (the cartesian product within each equal-key block). Emit results in ascending key order; within a key, pair each left value with each right value preserving the input order of both. Return the list of [left_value, right_value] pairs.
Examples
merge_join(left: list[list], right: list[list]) -> list[list]Example 1
Input
merge_join([[1, "a"], [2, "b"], [2, "c"]], [[2, "x"], [2, "y"], [3, "z"]])Output
[["b", "x"], ["b", "y"], ["c", "x"], ["c", "y"]]