Sorting II: Merge Sort

Merge sort is a divide-and-conquer sort that runs in O(n log n) by recursively splitting a list, sorting each half, and merging the sorted halves back together.

Core idea (3 steps)

• Divide: split the list into two halves at mid = len // 2.
• Conquer: sort each half by calling merge sort on it (recursion).
• Combine: merge the two sorted halves into one sorted list.
• Base case: a list of length 0 or 1 is already sorted; return it as-is. Without it, recursion never stops.
• Foundation fact: merging two already-sorted lists into one sorted list is easy and cheap.

The merge step

• Input: two lists that are each already sorted. Output: one sorted list with all items.
• Put a finger at the start of each list; compare, take the smaller, advance that finger; repeat until one runs out, then append the rest of the other.
• Cost: O(k) time and O(k) extra space for k total items (each item placed exactly once, new result list built).

left  [2, 4, 5]      finger i
right [1, 3, 6]      finger j
compare left[i] vs right[j] -> take smaller -> advance that finger
one side empties -> attach the rest of the other

Complexity

• Always splits down the middle and always does full merges, so time is the same in every case.
• Not in-place: needs room for a copy. Main tradeoff.

Stability

• Stable: equal-comparing items keep their original relative order.
• Guaranteed by the tie-break left[i] <= right[j] (take from left on ties, since left holds earlier items).
• Changing <= to < takes from the right on ties and breaks stability.

Gotchas

• Forgetting the base case (if len(items) <= 1) crashes with a recursion error.
• Slices must cover the whole list once: use items[:mid] and items[mid:]; items[mid+1:] silently drops the middle item.
• Use // (integer division) for mid, not /; a slice index must be a whole number.
• Do not assume in-place; it uses O(n) extra memory.
• Comparing incompatible types (mixing numbers and strings) raises TypeError.