Merge Sort
Also known as: mergesort
A divide-and-conquer sorting algorithm that splits a list in half, sorts each half recursively, then merges the sorted halves. One of the most efficient general-purpose sorting algorithms; used in many language standard libraries.
💡 Intuition
Split a messy deck of cards in half, sort each half, then interleave them back in order.
Core Idea
Merge sort guarantees O(n log n) performance regardless of input order.
🔬 Example
🎯 Why It Matters
One of the most efficient general-purpose sorting algorithms; used in many language standard libraries.
⚠️ Common Confusion
Merge sort uses extra memory proportional to the input size (unlike in-place sorts).
Related Concepts
Prerequisites
Next Steps
How Merge Sort Connects to Other Ideas
To understand merge sort, you should first be comfortable with sorting, recursion and efficiency. Once you have a solid grasp of merge sort, you can move on to bubble sort and binary search.
Go Deeper
Frequently Asked Questions
What is Merge Sort in CS Thinking?
A divide-and-conquer sorting algorithm that splits a list in half, sorts each half recursively, then merges the sorted halves.
Why is Merge Sort important?
One of the most efficient general-purpose sorting algorithms; used in many language standard libraries.
What do students usually get wrong about Merge Sort?
Merge sort uses extra memory proportional to the input size (unlike in-place sorts).
What should I learn before Merge Sort?
Before studying Merge Sort, you should understand: sorting, recursion, efficiency.