Merging two already-sorted lists in a single pass is the heart of merge sort and a first taste of the two pointers technique.
Given two lists a and b, each already sorted in non-decreasing order, return a new sorted list containing all elements of both.
Examples
Input: a = [1, 3, 5], b = [2, 4, 6]
Output: [1, 2, 3, 4, 5, 6]
Input: a = [1, 1, 3], b = [1, 2]
Output: [1, 1, 1, 2, 3]
Input: a = [], b = [7, 8]
Output: [7, 8]
Constraints
0 <= len(a), len(b) <= 1000- Aim for O(n + m) time with a single pass.
sorted(a + b)gives the right answer but is O((n+m) log(n+m)) and misses the point of the exercise.
Goals
- Walk two lists simultaneously with one index each
- Choose the smaller front element and advance only that pointer
- Append leftover elements once one list is exhausted