Merge Sort
A classic Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
Merge Sort Algorithm
Merge Sort: Level 0 (divide)
Starting Merge Sort with 7 elements
Current array: [38, 27, 43, 3, 9, 82, 10] (length: 7)
Divide, then conquer
Order the stages of merge sort.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
Is Merge Sort a stable sorting algorithm?
The short version
Imagine sorting a deck of cards. It's hard to sort 52 cards at once. So you split the deck until you have piles of 1 card (which are sorted!). Then you merge pairs of piles back together in order. Divide and Conquer!
In more depth
The Power of Divide and Conquer
Merge Sort is a perfect example of the Divide and Conquer strategy. It solves the problem of sorting by breaking it down into trivial sub-problems (sorting lists of size 1) and then combining the results.
Step-by-Step:
Why it matters
Merge Sort guarantees O(n log n) performance even in the worst case, making it highly predictable. It is also a Stable Sort, meaning it preserves the relative order of equal elements—crucial for real-world data like sorting spreadsheets by multiple columns.
When to reach for this
- When you need a **Stable Sort** (preserving order of duplicates)
- When sorting Linked Lists (random access is not required)
- When you need guaranteed O(n log n) performance regardless of input
- External Sorting (when data doesn't fit in memory)
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required