Merge Two Sorted Lists

Python data engineering interview problem. Difficulty: beginner. Pattern: Two Pointers. About 10 minutes. Free to practice.

Merge two sorted lists in linear time without calling sort. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

Imagine 2 lines of people, each already sorted by height from shortest to tallest. You want to merge them into one line that is also sorted. This is the 'merge' step that merge sort uses. Write a function merge_sorted(a, b) that takes two lists sorted from smallest to largest, and returns one list with all the values from both, also sorted from smallest to largest. You are not allowed to use sort() or sorted(). The two lists are already in order, so you should make use of that and finish in one pass, in time proportional to the total number of values (O(n + m)). Keep the print lines in the editor.

Requirements

• Return one list containing every value from a and b.
• The returned list must be sorted from smallest to largest.
• Do not call sort() or sorted().
• Look at each value only once. Do not sort the combined list afterwards.

Constraints

• a and b are both sorted in ascending order. Either of them can be empty.
• Duplicates are allowed. If both lists have a 3, both 3s appear in the result.
• Aim for time proportional to the length of a plus the length of b.

Examples

Input: merge_sorted([1, 3, 5], [2, 4, 6]) Output: [1, 2, 3, 4, 5, 6] Pointers advance through both sides.

Topics: lakebench, python, merge.

More Python interview questions · All interview problems · Learn data engineering