Insertion Sort is the algorithm Python's Timsort uses for arrays under 64 elements. Not just a teaching tool — it's in production in the world's most popular runtime.
🃏 The Core Idea
Pick up playing cards one by one. Each new card gets inserted into the correct position among the cards already in your hand — comparing right to left until it finds its spot.
📋 Example: [5, 3, 8, 1, 4]
- Take 3 → shift 5 → insert →
[3, 5, 8, 1, 4] - Take 8 → 8 > 5, no shift →
[3, 5, 8, 1, 4] - Take 1 → shift 8, 5, 3 → insert at start →
[1, 3, 5, 8, 4] - Take 4 → shift 8, 5 → insert after 3 →
[1, 3, 4, 5, 8]✅
💻 Code
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
JavaScript
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
⏱ Complexity
| Case | Time | Space | Stable |
|---|---|---|---|
| Best (sorted) | O(n) | O(1) | ✅ |
| Average | O(n²) | O(1) | ✅ |
| Worst (reversed) | O(n²) | O(1) | ✅ |
🆚 Full Comparison
| Algorithm | Best | Average | Worst | Stable |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | ✅ |
| Selection Sort | O(n²) | O(n²) | O(n²) | ❌ |
| Insertion Sort | O(n) | O(n²) | O(n²) | ✅ |
🏭 Why Used in Real Systems?
- Nearly sorted data → near-linear performance
- Small arrays → beats O(n log n) due to lower overhead
- Online algorithm → sorts a stream as data arrives
Part 9 of the Bitveen DSA Series. Full series at bitveen.com
Originally published at bitveen.com
Top comments (1)
Nice breakdown of insertion sort. It's interesting how Timsort uses it for small arrays because of its low overhead. For anyone working on similar DSA problems, PracHub has algorithm-focused coding banks that match the kind of problems you might see in real interviews. It's been more helpful than searching through random Glassdoor threads for me. People often dismiss it as just educational, but it's actually useful in production.