IntermediateSorting
Merge sort and partitioning, by hand
splits in half, sorts each half and merges them: every time. Partitioning moves the smaller items to the left in one pass.
The idea
Merge sort splits the list in half, sorts each half recursively, then merges the two sorted halves by repeatedly taking the smaller front item. There are log n levels of splits and n work per level: O(n log n).
Partitioning, the heart of and Sort Colors, walks the array once and swaps anything that belongs on the left into the next free left slot. One pass, no extra list.
Worked example
Merging [1, 4] and [2, 3]
- 1 vs 2 → take 1: [1]
- 4 vs 2 → take 2: [1, 2]
- 4 vs 3 → take 3: [1, 2, 3]
- The right half is empty → add what's left: [1, 2, 3, 4]
In code (Python)
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left, right = merge_sort(nums[:mid]), merge_sort(nums[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps equal items in order
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
return out + left[i:] + right[j:]Merge sort: O(n log n) time, . Partitioning: O(n) time, space.
How to spot it
- “Sort it yourself, no built-in sort” (Sort an Array).
- Group items into two or three kinds (Sort Colors, Sort Array By Parity).
- Counting pairs that are out of order: count them while you merge.
Common mistakes
- Merging with < instead of <=, so equal items swap places and the sort stops being stable.
- Quick sort with the first item as the on sorted input is : pick a random pivot.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →