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

🆚 Full Comparison

🏭 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