Chapter 4: DSA Insertion Sort
DSA Insertion Sort – Let’s learn this one properly, like I’m sitting next to you with a notebook, explaining slowly, drawing pictures with words, giving multiple examples, and telling you honestly where this algorithm is actually useful (because unlike Bubble and Selection sort, Insertion Sort is surprisingly practical in some real situations).
What is Insertion Sort?
Insertion Sort builds the sorted array one element at a time.
It is very similar to how most people sort a hand of playing cards:
- You pick one card at a time
- You insert it into its correct position among the cards you already have sorted in your hand
- You keep doing this until all cards are placed correctly
That’s exactly what Insertion Sort does with array elements.
Core idea in one sentence:
Take each element one by one and insert it into the already sorted left part at the correct position (by shifting larger elements to the right).
How Insertion Sort Works – Step by Step
Array: [5, 3, 8, 4, 2]
Goal: [2, 3, 4, 5, 8]
We consider the first element as already “sorted”.
Step 1: Sorted part = [5] Unsorted = [3, 8, 4, 2]
Take next element = 3 Compare with sorted part: 3 < 5 → insert 3 before 5
After step 1: [3, 5, 8, 4, 2] ↑↑ sorted
Step 2: Take next = 8 Compare: 8 > 5 → already in correct position (no shift needed)
After step 2: [3, 5, 8, 4, 2] ↑↑↑ sorted
Step 3: Take next = 4 Compare from right to left in sorted part:
4 < 8 → shift 8 right 4 < 5 → shift 5 right 4 > 3 → insert 4 here
After shifting: [3, 5, 8, 4, 2] → [3, 5, 8 → moved right] → [3, 4, 5, 8, 2]
After step 3: [3, 4, 5, 8, 2] ↑↑↑↑ sorted
Step 4: Take next = 2 Compare from right:
2 < 8 → shift 8 2 < 5 → shift 5 2 < 4 → shift 4 2 < 3 → shift 3 → insert 2 at beginning
After step 4: [2, 3, 4, 5, 8]
Done!
Visual Flow – Very Important to See the Pattern
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Initial: 5 3 8 4 2 After 1st: 3 5 8 4 2 ← 3 inserted before 5 After 2nd: 3 5 8 4 2 ← 8 already correct After 3rd: 3 4 5 8 2 ← 4 inserted between 3 and 5 After 4th: 2 3 4 5 8 ← 2 inserted at beginning |
Insertion Sort Code (very clean Python version)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
def insertion_sort(arr): # Start from second element (index 1) for i in range(1, len(arr)): key = arr[i] # the element we want to insert j = i - 1 # start comparing from the previous element # Move elements that are greater than key one position ahead while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] # shift right j -= 1 # Insert the key at correct position arr[j + 1] = key return arr # Example numbers = [64, 34, 25, 12, 22, 11, 90] print("Before:", numbers) insertion_sort(numbers) print("After: ", numbers) # Output: # Before: [64, 34, 25, 12, 22, 11, 90] # After: [11, 12, 22, 25, 34, 64, 90] |
Very Important – Time & Space Complexity
| Case | Time Complexity | When does it happen? |
|---|---|---|
| Best Case | O(n) | Array is already sorted (or almost sorted) |
| Average Case | O(n²) | |
| Worst Case | O(n²) | Reverse sorted array |
| Space Complexity | O(1) | In-place sorting — only uses a few variables |
Key point: Insertion Sort is the only simple sorting algorithm that becomes very fast (O(n)) when the array is already sorted or nearly sorted.
Comparison: Insertion vs Bubble vs Selection
| Feature | Insertion Sort | Bubble Sort | Selection Sort |
|---|---|---|---|
| Best case time | O(n) | O(n) with optimization | O(n²) |
| Worst case time | O(n²) | O(n²) | O(n²) |
| Number of swaps | Depends (can be many) | Many | Very few (~n) |
| Stable? | Yes | Yes | No |
| Adaptive? | Yes (fast on sorted) | Yes (with flag) | No |
| Best when… | Nearly sorted data | Learning only | Expensive swaps |
Where is Insertion Sort actually used in real life?
Unlike Bubble and Selection sort, Insertion Sort is not just for learning — it appears in real systems:
- Small arrays (n ≤ 50–100) — very fast in practice
- Nearly sorted data (many algorithms use it here)
- Online sorting (data coming one by one)
- Hybrid sorting algorithms:
- Timsort (used in Python & Java) uses Insertion Sort for small chunks
- Many internal implementations switch to Insertion Sort for very small subarrays
- When memory writes/swaps are expensive
- In some embedded systems or real-time systems with small data
Summary – Insertion Sort in one line each
- Builds sorted portion from left to right
- Takes one element at a time and inserts it into correct position in the sorted part
- By shifting all larger elements one position right
- Very efficient when array is already sorted or almost sorted (O(n))
- Stable sorting algorithm
- In-place (O(1) extra space)
- One of the few simple sorts that is actually used in real implementations
Now you’ve seen all three classic simple sorts:
- Bubble → keeps bubbling largest to end
- Selection → keeps selecting smallest and putting in front
- Insertion → keeps inserting next element in correct place
Which one would you like to go deeper into next?
Options:
- Common interview questions using Insertion Sort logic
- How to implement Binary Insertion Sort (faster insertion using binary search)
- When interviewers ask you to sort with constraints
- Comparison of all three simple sorts with more examples
- Moving to next topic: Two Pointers or Kadane’s algorithm on arrays
Just tell me what you want next — I’ll explain it in the same detailed, friendly way! 😊
