Insertion Sort Explained Simply — Algorithm, Code & Examples

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