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]

  1. Split: [5, 2] and [4, 1]. Split again: [5] [2] and [4] [1], single items, already sorted.
  2. Merge [5] and [2] → [2, 5]. Merge [4] and [1] → [1, 4].
  3. 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.

merge_sort(nums):
if 0 or 1 items: return nums
left ← merge_sort(first half)
right ← merge_sort(second half)
while both have items:
take the smaller front item into out
return out + whatever is left

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]

05
12
24
31

Solution · Pythonline 4

def merge_sort(nums):
if len(nums) <= 1: # base case: already sorted
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = 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 (stable)
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return 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.

Practise it · before the Sorting problems

Sort with merge sort

Return nums in ascending order. Write yourself: no built-in sort.

Input nums = [5, 2, 4, 1]

Output [1, 2, 4, 5]

Input nums = [3, 3, -1]

Output [-1, 3, 3]

Pass every test and this concept is marked as known on the roadmap and on every problem that needs it.

Your code

Tab / Shift+Tab indent · ⌘/Ctrl+/ comments · ⌘/Ctrl+Enter runs · Esc leaves the editor

Stuck?