Краткий вывод: код некорректен — отсутствует операция слияния, функция просто рекурсивно разбивает список и снова склеивает куски в исходном порядке. Временная сложность теоретически совпадает с классическим merge sort, но из‑за многократного копирования через срезы и конкатенацию наблюдается значительный накладной расход по времени и памяти.
Проблемы в коде
- Нет шага слияния: вместо сравнивания элементов двух отсортированных половин используется просто `return left + right`, поэтому итоговый список остается в исходном порядке (фактически вы возвращаете копию входа).
- Использование срезов `arr` копирует данные при каждом вызове — большие накладные расходы по времени и памяти.
- Операция конкатенации `left + right` также копирует элементы (стоимость $\Theta (n)$ на каждом слиянии).
- Итог: много выделений памяти и копирований, что плохо для больших списков.
Асимптотика (для предложённого варианта)
- Рекуррентное соотношение (логически) выглядит как $T(n)=2T(n/2)+O(n)$, отсюда классическая оценка $T(n)=O(n\log n)$.
- Однако из‑за срезов/конкатенаций суммарная работа по копированию и выделению буферов даёт серьёзные константы и дополнительную нагрузку (внешне суммарная работа копирования может быть порядка $O(n\log n)$ по числу скопированных элементов), а практическая эффективность падает.
- Дополнительная память: в правильной реализации merge sort — $O(n)$ дополнительной памяти; в текущей реализации — много временных списков и копий, что увеличивает накладные расходы.
Исправление и оптимизация для больших списков
- Реализовать настоящий шаг слияния двух отсортированных половин, не создавая лишних срезов на каждом уровне.
- Использовать один вспомогательный массив (буфер) длины $n$ и передавать индексы (левой и правой границы) в рекурсию, либо итеративный (bottom‑up) вариант, чтобы снизить расход памяти и вызовов.
- Для больших списков в Python предпочтительнее использовать встроенный `.sort()` / `sorted()` (Timsort), которые оптимизированы и стабильны.
Пример корректной реализации (рекурсивная, с одним вспомогательным массивом):
def merge_sort(arr):
n = len(arr)
if n <= 1:
return arr
aux = [None] * n
def _merge_sort(l, r):
if r - l <= 1:
return
m = (l + r) // 2
_merge_sort(l, m)
_merge_sort(m, r)
i, j, k = l, m, l
while i < m and j < r:
if arr[i] <= arr[j]:
aux[k] = arr[i]; i += 1
else:
aux[k] = arr[j]; j += 1
k += 1
while i < m:
aux[k] = arr[i]; i += 1; k += 1
while j < r:
aux[k] = arr[j]; j += 1; k += 1
arr[l:r] = aux[l:r]
_merge_sort(0, n)
return arr
Сложности этой реализации: время $O(n\log n)$, дополнительная память $O(n)$, меньшие накладные расходы по сравнению с версией на срезах.
Рекомендация: для реальных задач на больших массивах используйте встроенный сортировщик Python (`arr.sort()` / `sorted(arr)`), он обычно быстрее и экономичнее по памяти.