Insertion Sort
Visualize Insertion Sort, an adaptive algorithm that builds the sorted array one item at a time.
Ready to sort
Intuition
Think of sorting playing cards in your hand. You pick up one card at a time and insert it into its correct position among the cards you're already holding.
Concept
- Strategy: Split the list into sorted (left) and unsorted (right). Pick element from unsorted, shift larger elements in sorted right, insert element.
- Adaptive: Runs in O(N) time if the input is already sorted.
- Stable: Preserves the relative order of equal elements.
How it Works
Algorithm:
- Assume index 0 is sorted.
- Take element at index
i(Key). - Compare Key with elements at
i-1, i-2.... - If element > Key, shift it right.
- Insert Key when smaller element found or start reached.
Step-by-Step Breakdown
Watch the visualization:
- Blue Bar (Key): The element currently being inserted.
- Red Bars: Elements being shifted to make space.
- Green Bars: The sorted portion of the array.
Trace: [12, 11, 13, 5, 6]
Key is 11. Compare with sorted predecessor 12.
Key: 11
Is 12 > 11? YES.
Shift 12 ->
Move 12 to position 1. Reached start.
[12, 12, ...]
Insert Key (11) at position 0.
[11, 12, 13, ...]
When to Use
- Small/Almost Sorted Data: Extremely efficient (O(N)) for nearly sorted arrays.
- Online Sorting: Can sort data as it arrives (streaming).
When NOT to Use
- Large Random Lists: O(N²) time complexity makes it slow.
- Reverse Sorted: Worst-case scenario.
How to Identify
"Sort online", "Data is nearly sorted".
Sample Problems
Frequently Asked Questions
When is Insertion Sort most efficient?
Insertion Sort is highly efficient for small datasets and for arrays that are already substantially sorted (nearly-sorted data).
What is the time complexity of Insertion Sort?
The worst-case complexity is O(n²), but the best-case (for a sorted array) is O(n).
Is Insertion Sort an online algorithm?
Yes, it can sort a list as it receives it, making it ideal for streaming data setup.