В главе сортировка слиянием упоминается как соперник быстрой сортировки: у неё O(n log n) даже в худшем случае. Допишите её. Список делится пополам, половины сортируются рекурсивно, а затем сливаются в один упорядоченный список за O(n). Пропуски помечены # TODO.
merge([1, 4, 9], [2, 3, 10]) # [1, 2, 3, 4, 9, 10]
merge_sort([5, 2, 8, 2, 1]) # [1, 2, 2, 5, 8]merge работает за O(len(left) + len(right)), без sorted и .sort().Заготовка задачи обновилась с тех пор, как вы сохранили свой код.
Сбросить редактор к заготовке? Ваш код будет удалён.
def merge(left: list[int], right: list[int]) -> list[int]:
"""Сливает два отсортированных списка в один отсортированный."""
result: list[int] = []
i = j = 0
while i < len(left) and j < len(right):
# TODO: возьмите меньший из left[i] и right[j], сдвиньте его указатель
break
# TODO: добавьте в result то, что осталось в left и в right
return result
def merge_sort(items: list[int]) -> list[int]:
"""Возвращает новый отсортированный список (сортировка слиянием)."""
if len(items) < 2:
return list(items)
mid = len(items) // 2
# TODO: отсортируйте половины рекурсивно и слейте их
return list(items)Вывод обрезан: показаны первые строки.
def test_merge_example():
"""merge: [1, 4, 9] + [2, 3, 10]"""
got = merge([1, 4, 9], [2, 3, 10])
assert got == [1, 2, 3, 4, 9, 10], f"получено {got!r}"
def test_merge_empty_sides():
"""merge: одна из половин пустая"""
assert merge([], [1, 2]) == [1, 2], f"merge([], [1, 2]) → {merge([], [1, 2])!r}"
assert merge([3], []) == [3], f"merge([3], []) → {merge([3], [])!r}"
assert merge([], []) == [], f"merge([], []) → {merge([], [])!r}"
def test_merge_uneven():
"""merge: одна половина закончилась намного раньше"""
got = merge([1, 2], [3, 4, 5, 6])
assert got == [1, 2, 3, 4, 5, 6], f"получено {got!r}"
def test_merge_duplicates():
"""merge: равные элементы в обеих половинах"""
got = merge([2, 2, 5], [2, 5, 5])
assert got == [2, 2, 2, 5, 5, 5], f"получено {got!r}"
def test_sort_example():
"""merge_sort: [5, 2, 8, 2, 1]"""
got = merge_sort([5, 2, 8, 2, 1])
assert got == [1, 2, 2, 5, 8], f"получено {got!r}"
def test_sort_edges():
"""merge_sort: пустой список и один элемент"""
assert merge_sort([]) == [], f"получено {merge_sort([])!r}"
assert merge_sort([7]) == [7], f"получено {merge_sort([7])!r}"
def test_sort_bigger():
"""merge_sort: 500 чисел с повторами"""
data = [(i * 97) % 61 - 30 for i in range(500)]
got = merge_sort(data)
assert got == sorted(data), f"начало: {got[:6]}"
def test_input_not_changed():
"""Исходный список не изменяется"""
data = [3, 1, 2]
merge_sort(data)
assert data == [3, 1, 2], f"список изменился: {data!r}"Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 merge_sort.py — тесты те же, результат покажет ✓ / ✗ и итог.
Базовый случай такой же, как у быстрой сортировки: список длины 0 или 1.
Слияние: два указателя i и j. Каждый раз берите меньший из left[i] и right[j] и сдвигайте его указатель.
Когда одна половина закончилась, остаток другой добавьте целиком. При равенстве берите из левой — так порядок равных сохранится.
def merge(left: list[int], right: list[int]) -> list[int]:
"""Сливает два отсортированных списка в один отсортированный."""
result: list[int] = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def merge_sort(items: list[int]) -> list[int]:
"""Возвращает новый отсортированный список (сортировка слиянием)."""
if len(items) < 2:
return list(items)
mid = len(items) // 2
return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))