Сортировка слиянием — это разделяй и властвуй алгоритм, стабильная сортировка, работающая за гарантированное время O(n log n). Она делит массив пополам, рекурсивно сортирует каждую половину, а затем объединяет две отсортированные половины.
Одиночный элемент уже отсортирован (базовый случай). Слияние двух отсортированных списков выполняется за линейное время, и мы выполняем log n уровней слияния.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
Идеально, когда вам нужна стабильность или гарантированное O(n log n), а также для связных списков и внешней сортировки огромных файлов. Дополнительная памяти O(n) — его основной недостаток.
Сортировка слиянием гарантирует O(n log n) независимо от входных данных, в отличие от наихудшего случая O(n²) у быстрой сортировки.
Её стабильность сохраняет относительный порядок равных ключей, что важно при сортировке по нескольким ключам.
Этап слияния — это переиспользуемая примитивная операция, а структура разделяй и властвуй — это шаблон, который вы будете переиспользовать повсюду.