Python · Theory

Merge Sort in Python

Theory

81/268

Merge Sort in Python

Merge Sort orders a list. Say the idea in plain words, then complexity. Bubble/insertion/selection are O(n²) teaching sorts. Merge and heap are O(n log n). Python’s built-in sort is Timsort (O(n log n), very fast in practice).

Dry-run Merge Sort on a tiny list like [4, 1, 3, 2] on the board. Interviewers care that you can trace one pass, not that you recite a textbook page.

For Merge Sort in real code: sorted(a) / a.sort() is what you use. Write the algorithm only when they ask you to implement it.

Merge Sort in Python — output — [1, 2, 3, 4]. Split, sort halves, merge. O(n log n).

Exam tip

Idea + complexity + one tiny trace. Then say when to use built-in sort.

Example

# Merge Sort in Python
def merge(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    L, R = merge(a[:mid]), merge(a[mid:])
    o, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            o.append(L[i]); i += 1
        else:
            o.append(R[j]); j += 1
    return o + L[i:] + R[j:]
print(merge([4, 1, 3, 2]))

Merge Sort in Python — output: [1, 2, 3, 4]. Split, sort halves, merge. O(n log n).

Short notes

DefMerge Sort puts items in order.
RuleMerge Sort — know idea + O(...).
RememberMerge Sort — real code uses sorted() / Timsort.
TrapMerge Sort — implementing O(n²) in production when sorted() exists.

# Merge Sort in Python def merge(a): if len(a) <= 1: return a mid = len(a) // 2 L, R = merge(a[:mid]), merge(a[mid:]) o, i, j = [], 0, 0 while i < len(L) and j < len(R): if L[i] <= R[j]: o.append(L[i]); i += 1 else: o.append(R[j]); j += 1 return o + L[i:] + R[j:] print(merge([4, 1, 3, 2]))

Merge Sort in Python

Example

Short notes

Questions

Merge Sort in Python

Example

Short notes

Questions