Объединение двух отсортированных списков
Python
Middle
Ozon
01.01.2025
Напишите функцию `merge_sorted(a: list[int], b: list[int]) -> list[int]`, которая объединяет два **отсортированных по возрастанию** списка в один отсортированный список.
Нельзя просто делать `sorted(a + b)`, нужно реализовать алгоритм слияния за O(len(a) + len(b)).
**Пример:**
```python
merge_sorted([1,3,5], [2,4,6]) -> [1,2,3,4,5,6]
```
Ответы
Решение 1
```python
def merge_sorted(a: list[int], b: list[int]) -> list[int]:
i = j = 0
result: list[int] = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
if i < len(a):
result.extend(a[i:])
if j < len(b):
result.extend(b[j:])
return result
```