Коротко: приведённый код не выполняет операцию слияния двух отсортированных частей — он просто конкатенирует списки, поэтому результат остаётся неотсортированным. Далее — почему, сложность и исправление.
Почему некорректно
- В строке `return left + right` выполняется простая конкатенация списков, а не поэлементное слияние с выбором меньшего элемента из двух частей. Пример: для $a=[1,4,2,3]$ рекурсивно получится $left=[1,4]$, $right=[2,3]$, а `left + right` даст $[1,4,2,3]$ — неотсортированный результат.
Сложность исходного фрагмента
- Временная: рекуррентное соотношение при разделении на половины и конкатенации длины $n$ — $T(n)=2T(n/2)+\Theta (n)$, поэтому $T(n)=\Theta (n\log n)$.
- Память: из-за срезов `a[:mid]` и `a[mid:]` и выделения новых списков при конкатенации потребление дополнительной памяти — $\Theta (n)$ (пиковый доп. объём порядка $n$; глубина стека рекурсии $\Theta (\log n)$).
Исправленная реализация (корректное слияние двух отсортированных списков)
```python
def merge(left, right):
i = j = 0
merged = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
if i < len(left):
merged.extend(left[i:])
if j < len(right):
merged.extend(right[j:])
return merged
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
return merge(left, right)
```
Анализ исправленной версии
- Время: на каждом уровне слияний выполняется линейная работа $\Theta (n)$, глубина рекурсии $\Theta (\log n)$. Итого $T(n)=\Theta (n\log n)$.
- Память: дополнительный массив для слияния размера $n$ и стек глубиной $\Theta (\log n)$, поэтому дополнительная память $\Theta (n)$. Если нужно уменьшить количество копирований, можно реализовать версию с общим буфером (aux array) и индексами — тогда тоже требуется $\Theta (n)$ дополнительной памяти, но с меньшим числом выделений.