def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
out = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return outVariables
n- length of the input array
Explanation
The recursion tree has **log n** levels, and each level does O(n) total work merging - **O(n log n)** time, regardless of input order. Each merge needs a buffer the size of the slice; the live slices across the recursion sum to O(n) - **O(n)** space. This is the classic divide-and-conquer trade: linearithmic time at the cost of linear extra memory.