Merge Two Sorted Lists

Given two sorted lists, merge them into one sorted list efficiently.

merge sorting lists

Write a function `merge_sorted_lists(a, b)` that takes two lists of integers, `a` and `b`, each already sorted in non-decreasing order. The function should return a new list that contains all elements from both lists, sorted in non-decreasing order. Do not modify the input lists. Your solution should run in O(len(a) + len(b)) time and use O(1) extra space (besides the output list).

Constraints

- 0 <= len(a), len(b) <= 10^5
- Each element is an integer.
- Input lists are sorted in non-decreasing order.
- Expected time complexity: O(len(a) + len(b)).

Example

```python
>>> merge_sorted_lists([1, 3, 5], [2, 4, 6])
[1, 2, 3, 4, 5, 6]
>>> merge_sorted_lists([1, 2, 3], [])
[1, 2, 3]
>>> merge_sorted_lists([], [1, 1, 2])
[1, 1, 2]
>>> merge_sorted_lists([], [])
[]
```

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

To avoid O(n log n) sorting, notice both inputs are already sorted. Why not use two pointers?

Compare the smallest remaining element of each list and take the smaller one.

After one list is exhausted, append the remaining elements from the other list.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.