Know this before you start: “Merge sort: split, sort both halves, merge”
Merge sort: split, sort, merge
Split the array in half, sort each half the same way, then merge the two sorted halves by repeatedly taking the smaller front item. Always .
The idea
It's : an array of 0 or 1 items is already sorted (the ). Anything longer, split in the middle and sort both halves.
Merging two sorted lists is easy: compare their fronts, take the smaller, repeat. Each item is taken once, so a merge is .
Halving gives about log₂ n levels, and each level merges n items in total: O(n log n), even in the . It's stable too: equal items keep their order.
Worked example
Merge sort [5, 2, 4, 1]
- Split: [5, 2] and [4, 1]. Split again: [5] [2] and [4] [1], single items, already sorted.
- Merge [5] and [2] → [2, 5]. Merge [4] and [1] → [1, 4].
- Merge [2, 5] and [1, 4]: take 1, then 2, then 4, then 5 → [1, 2, 4, 5].
Pseudocode
The steps in plain words. ← means “set to”; indentation shows what's inside what.
See it run
The worked example, step by step, beside the Python. The highlighted line is the one running.
Step-by-step
nums = [5, 2, 4, 1]
Solution · Pythonline 4
def merge_sort(nums):if len(nums) <= 1: # base case: already sortedreturn numsmid = len(nums) // 2left = merge_sort(nums[:mid])right = merge_sort(nums[mid:])out, i, j = [], 0, 0while i < len(left) and j < len(right):if left[i] <= right[j]: # <= keeps equal items in order (stable)out.append(left[i]); i += 1else:out.append(right[j]); j += 1return out + left[i:] + right[j:] # one side may have items left print(merge_sort([5, 2, 4, 1])) # [1, 2, 4, 5]Step 1 of 8· line 4
4 items: split in the middle into [5, 2] and [4, 1].
- compared with
- inside the window
O(n log n) time in every case, O(n) for the merged lists.
When you'll use it
- Sorting when you must write it yourself, sorting , counting inversions (“how many pairs are out of order”), merging k sorted lists.
In the wild · Every “Sort by” button: Sorting a spreadsheet by price, then by name, needs a stable sort, which is why Python and JavaScript both use merge-sort-based TimSort.
Common mistakes
- Forgetting the leftovers after the merge loop: one half usually runs out first.
- Using < instead of <= when merging, which makes it unstable.