Проблемы в приведённой реализации
1) Логическая:
- Вместо слияния отсортированных половин код делает конкатенацию `left + right`. Это не гарантирует отсортированность результата (только в частном случае, когда все элементы `left` ≤ все элементы `right`).
2) Производительные и по памяти:
- Срезы `a[:mid]` и `a[mid:]` создают копии подмассивов на каждом уровне рекурсии — много аллокаций и копирований.
- Операция `left + right` тоже копирует элементы при каждом возврате.
- Избыточные копирования увеличивают константные затраты; при наивной реализации наблюдается множество выделений (временные и память), что замедляет работу на больших массивах.
- Глубина рекурсии — $\mathcal{O}(\log n)$, что нормально, но срезы и конкатенации увеличивают нагрузку.
Исправления
1) Минимальное исправление (оставить срезы, но правильно сливать):
- Реализовать функцию merge, которая за $\mathcal{O}(n)$ объединяет два отсортированных списка в один.
Пример:
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
i = j = 0
res = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i]); i += 1
else:
res.append(right[j]); j += 1
res.extend(left[i:])
res.extend(right[j:])
return res
Сложности для этой версии:
- Время: $\mathcal{O}(n\log n)$.
- Память/алокации: много временных копий из-за срезов и конкатенаций (константно хуже, но асимптотически пиковая дополнительная память обычно $\mathcal{O}(n)$; количество выделений — $\Theta (n\log n)$ за всё время выполнения).
2) Оптимальная реализация (меньше копирований, $\mathcal{O}(n)$ дополнительной памяти):
- Использовать сортировку с индексами и единый вспомогательный буфер для слияния, либо делать in-place с буфером размера $n$. Это уменьшает количество аллокаций и копирований.
Пример (in-place с буфером):
def merge_sort_inplace(a):
n = len(a)
buf = [0] * n
def _sort(l, r):
if r - l <= 1:
return
m = (l + r) // 2
_sort(l, m)
_sort(m, r)
i, j, k = l, m, l
while i < m and j < r:
if a[i] <= a[j]:
buf[k] = a[i]; i += 1
else:
buf[k] = a[j]; j += 1
k += 1
while i < m:
buf[k] = a[i]; i += 1; k += 1
while j < r:
buf[k] = a[j]; j += 1; k += 1
a[l:r] = buf[l:r]
_sort(0, n)
return a
Сложности для оптимальной версии:
- Время: $\mathcal{O}(n\log n)$.
- Доп. память: $\mathcal{O}(n)$ (буфер) + стек рекурсии $\mathcal{O}(\log n)$.
- Меньше аллокаций и быстрее на больших данных по сравнению с версией на срезах.
Краткое резюме
- Логическая ошибка: нужно сливать, а не конкатенировать.
- Производительная проблема: срезы и конкатенации приводят к множественным копированиям и аллокациям.
- Рекомендация: реализовать корректный merge; для лучшей производительности — использовать индексы и единый буфер; асимптотическая сложность времени остаётся $\mathcal{O}(n\log n)$, оптимальная дополнительная память — $\mathcal{O}(n)$.