Merge Sort
Learn Merge Sort, a divide-and-conquer algorithm that guarantees O(N log N) performance.
38
27
43
3
9
82
10
Ready to sort
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
If you have a messy stack of papers, you can split it iteratively until you have single papers (which are trivially sorted). Then you merge small sorted stacks into larger ones until you have one sorted stack.
Concept
- Divide & Conquer: Recursively splits the array into two halves until size 1.
- Merge: The core operation. Merges two sorted sub-arrays into a single sorted array.
- Complexity: Guarantees O(N log N) time complexity in all cases.
How it Works
Algorithm:
- Find middle index.
- Recursively sort left half.
- Recursively sort right half.
- Merge the two sorted halves into a temporary array (or overwrite).
Step-by-Step Breakdown
Watch the visualization:
- Blue Highlight: Visualizes the current sub-array being merged (Deep in recursion).
- Red Bar: Value being overwritten in the original array from the sorted result.
- Green: Fully sorted array at the end.
When to Use
- Large Datasets: Guaranteed efficiency where O(N²) sorts fail.
- Linked Lists: Can sort linked lists in O(N log N) without extra space.
- Stable Sort Needed: When relative order matters.
When NOT to Use
- Space Constraints: Requires O(N) auxiliary space for arrays.
- Very Small N: Overhead of recursion makes it slower than Insertion Sort for tiny arrays.
How to Identify
"Guaranteed O(N log N)", "Sort Linked List", "External Sorting".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.