1. One-Liner
Insertion Sort takes each element in order and inserts it into the correct position among the already-sorted elements to its left.
2. The Problem It Solves
It excels on small n and nearly sorted arrays: low constant factors, stable, in-place — often used as a subroutine in Tim Sort and fast QuickSort hybrids.
3. The Core Idea
Sort a hand of cards: pick the next card from the table and slide it left until it fits between the two neighbors where it belongs.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. | Start at i = 1; subarray 0..i-1 is sorted |
| 2. | key = a[i]; set j = i-1 |
| 3. | While j >= 0 and a[j] > key, shift a[j] right |
| 4. | Write key into the gap |
| 5. | Increment i |
5. Dry Run Example
[4, 2, 5, 1]: insert 2 before 4 → [2,4,5,1]; 5 stays; insert 1 → [1,2,4,5].
6. Key Properties
| Property | Value |
|---|---|
| Adaptive | O(n) comparisons if already sorted |
| Stable | Yes |
| Online | Can process a stream one item at a time |
7. Where It Is Used
| Company / System | How They Use It |
|---|---|
Python list.sort / Timsort | Small-run insertion merge |
Java Arrays.sort (objects) | TimSort merge + insertion |
8. Interview Tips
Highlight adaptive behavior; binary insertion reduces comparisons but not shifts; why it’s a building block of Tim Sort.
9. Comparison with Other Algorithms
| Algorithm | Nearly sorted | Random large n |
|---|---|---|
| Insertion | Excellent | Poor |
| Merge | Good | Excellent |
| Quick | Depends on pivot | Excellent average |
10. Complexity
| Metric | Value |
|---|---|
| Time (Best) | O(n) |
| Time (Average) | O(n²) |
| Time (Worst) | O(n²) |
| Space | O(1) |
| Stable? | Yes |
Implementation Example (PYTHON)
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr