Skip to content
Back to AlgorithmsAll lessons

Algorithms

Merge Sort

O(n log n) time — much faster than the simple sorts on big data · O(n) extra space for the merges.

The idea, in plain English

Merge sort uses a method called 'divide and conquer' — you split a big problem into small ones, solve those, then combine the answers. Split the list in half, then in half again, until each piece holds one item (already sorted by itself). Then merge the small sorted pieces back together in order.

How it works

  1. 1Keep splitting the list in half until each piece has one item.
  2. 2Merge two sorted pieces by always taking the smaller of the two front items.
  3. 3Keep merging pairs together until the whole list is one sorted list.

When you'd use it

Use it for large lists where you need reliably fast sorting. Also use it when you need a stable sort, one that keeps equal items in their original order.

Common beginner mistakes

  • Forgetting to copy the leftover items from one half after the other half runs out.
  • Splitting the list wrong and dropping the middle item.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Before: 5 2 9 1 5 6
Sorted: 1 2 5 5 6 9

See it in motion

Watch it sortMerge sortO(n log n) time — much faster than the simple sorts on big data · O(n) extra space for the merges.

Ready. Press play to watch it sort.

0
Comparisons
0
Writes
0/32
Step
0.0s
Time
ComparingSwappingSorted

Not sure this is the right topic? See the learning paths → or where this leads →