Complexity Analysis

#13 — Recursion

def merge_sort(arr):
    if len(arr) &lt;= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    result = []
    i = j = 0
    while i &lt; len(a) and j &lt; len(b):
        if a[i] &lt;= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

What is the time and space complexity?

Work it out before scrolling down.

Time

O(n log n)

Space

O(n)

How to derive it

The array is halved log n times (tree depth = log n). At each level of recursion, every element is visited once during merging → O(n) work per level. Total: O(n) × O(log n) = O(n log n). Space: the merge creates temporary arrays totaling O(n) at each level, plus O(log n) stack depth.

← #12 #14 →