Merge Sort
Merge sort is a divide-and-conquer sorting algorithm that guarantees O(N log N) performance.
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".
Applying for software engineering roles? Free, no sign-up: