Sort-merge inner join

Write codeHard35 minSnowflake and Databricks style

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
Inputmerge_join([[1, "a"], [2, "b"], [2, "c"]], [[2, "x"], [2, "y"], [3, "z"]])
Output[["b", "x"], ["b", "y"], ["c", "x"], ["c", "y"]]