Chapter 46: DSA Insertion Sort Time Complexity
DSA Insertion Sort Time Complexity Let’s talk about this very calmly, slowly and thoroughly — like we are sitting together and I’m explaining it to you on paper so you really understand it deeply and never forget.
Insertion Sort is one of those algorithms where time complexity changes dramatically depending on whether the data is already sorted, almost sorted, random, or reverse sorted. This makes it very interesting (and very frequently asked in interviews).
Quick reminder – How Insertion Sort actually works
Insertion Sort builds the sorted part from left to right, one element at a time.
For each new element:
- Take the current element (the one we want to insert)
- Compare it from right to left with the already sorted part
- Shift all larger elements one position right to make space
- Place the element in the correct position
Very small example (so we can count operations):
Array: 5 3 8 4 2
Step 1: 5 is already sorted Sorted part: 5
Step 2: Take 3 Compare with 5 → 3 < 5 → shift 5 right Place 3 → 3 5
Step 3: Take 8 8 > 5 → already in correct place 3 5 8
Step 4: Take 4 4 < 8 → shift 8 4 < 5 → shift 5 4 > 3 → place 4 3 4 5 8
Step 5: Take 2 2 < 8 → shift 8 2 < 5 → shift 5 2 < 4 → shift 4 2 < 3 → shift 3 Place 2 → 2 3 4 5 8
Time Complexity – Three Cases in Detail
Insertion Sort behaves very differently depending on the initial order of the array.
We always look at number of comparisons and number of shifts (both are the main operations).
| Case | When does it happen? | Number of comparisons (approx) | Number of shifts (approx) | Time Complexity | Real feeling |
|---|---|---|---|---|---|
| Best Case | Array is already sorted | n − 1 | 0 | O(n) | Very fast – almost linear |
| Average Case | Random / shuffled order | ~ n² / 4 | ~ n² / 4 | O(n²) | Quadratic – slow for large n |
| Worst Case | Array is reverse sorted | n(n−1)/2 | n(n−1)/2 | O(n²) | Maximum work – very slow |
1. Best Case – Already sorted array
Example: 2 3 4 5 8
For each new element:
- Compare with previous one → it’s already larger → no shift
- Only 1 comparison per element
Total comparisons = n − 1 Total shifts = 0
Time complexity = O(n) This is why Insertion Sort is called adaptive — it becomes very fast on already (or nearly) sorted data.
2. Worst Case – Reverse sorted array
Example: 8 5 4 3 2
For each new element:
- It has to be compared with all previous elements (because it’s smaller than all of them)
- All previous elements must be shifted right by one position
For i-th element (1-based):
- Comparisons = i
- Shifts = i
Total comparisons = 1 + 2 + 3 + … + (n−1) = n(n−1)/2 Total shifts ≈ n(n−1)/2
Time complexity = O(n²)
3. Average Case – Random order
In a random permutation:
On average, each new element needs to be compared and shifted about half the length of the already sorted part.
For i-th element → average comparisons & shifts ≈ i/2
Total ≈ Σ (i/2) from i=1 to n−1 ≈ n² / 4
Time complexity = O(n²)
4. Exact Comparison & Shift Count Formula
For array of size n:
- Best case Comparisons = n − 1 Shifts = 0
- Worst case Comparisons = n(n−1)/2 Shifts = n(n−1)/2
- Average case Comparisons ≈ n² / 4 Shifts ≈ n² / 4
5. Quick Visual Table – How it grows
| n | Best Case comparisons | Average comparisons (≈) | Worst Case comparisons | Feeling for worst case |
|---|---|---|---|---|
| 10 | 9 | ~25 | 45 | very fast |
| 100 | 99 | ~2,500 | 4,950 | acceptable |
| 1,000 | 999 | ~250,000 | 499,500 | starting to feel slow |
| 10,000 | ~10,000 | ~25 million | ~50 million | usually too slow |
| 100,000 | ~100,000 | ~2.5 billion | ~5 billion | practically unusable |
6. Summary – What you should say in interviews
“Insertion Sort has O(n²) time complexity in the average and worst cases because, on average, each element needs to be compared and shifted approximately half the length of the already sorted portion, leading to roughly n²/4 operations. In the best case (when the array is already sorted), it only performs n−1 comparisons and 0 shifts, resulting in O(n) time — this makes Insertion Sort adaptive. Because of the quadratic behavior in most cases, Insertion Sort is efficient only for small arrays (n < 50–100) or for nearly sorted data.”
7. Quick Cheat Sheet – Insertion Sort
| Question | Answer |
|---|---|
| Worst-case time complexity | O(n²) |
| Best-case time complexity | O(n) |
| Average-case time complexity | O(n²) |
| Space complexity | O(1) (in-place) |
| Stable? | Yes |
| Adaptive? | Yes (very good on nearly sorted data) |
| When to use | Small n, nearly sorted data, learning purposes |
Do you want to continue with any specific part?
Very common follow-up questions:
- Why is Insertion Sort stable while Selection Sort is not?
- Insertion Sort vs Bubble Sort – which is better in practice?
- How many shifts exactly in best / average / worst case?
- Can Insertion Sort be made faster? (binary insertion sort)
- Mathematical derivation of n²/4 average case
Just tell me which one you want next — I’ll explain it in the same calm, detailed, teacher style with clear examples 😊
