Insertion Sort

March 31, 2026

#insertion-sort #sorting #algorithms #data-structures #interviewing

Introduction

Insertion Sort builds a sorted array one element at a time by picking each element and inserting it into its correct position among the already-sorted elements. It’s exactly how most people sort a hand of playing cards — you pick up one card at a time and slide it into the right spot.

Despite being O(n²) in the worst case, Insertion Sort is genuinely useful. It’s the fastest algorithm for small arrays and nearly-sorted data, which is why many standard library sort implementations (like TimSort) use it as a building block. You should know Arrays and Big-O Notation before reading this.

Insertion Sort is O(n) on nearly-sorted data and has very low overhead, making it the practical choice for small arrays. Many hybrid sorting algorithms switch to Insertion Sort for subarrays below ~10-20 elements.

How it works

[5, 3, 8, 1, 2]

Start: [5] is trivially sorted

Insert 3: 3 < 5, shift 5 right → [3, 5, 8, 1, 2]
Insert 8: 8 > 5, stays         → [3, 5, 8, 1, 2]
Insert 1: 1 < 8, 1 < 5, 1 < 3 → [1, 3, 5, 8, 2]
Insert 2: 2 < 8, 2 < 5, 2 < 3 → [1, 2, 3, 5, 8]

Done: [1, 2, 3, 5, 8]

At each step, everything to the left of the current element is already sorted. We shift elements right until we find the correct spot.

Implementation

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

console.log(insertionSort([5, 3, 8, 1, 2]));  // [1, 2, 3, 5, 8]

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

print(insertion_sort([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

public static int[] insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

Complexity analysis

Case	Time	When
Best	O(n)	Already sorted — inner loop never runs
Average	O(n²)	Random order
Worst	O(n²)	Reverse sorted — every element shifts all the way

Space: O(1) — sorts in place.

Stable: Yes — equal elements maintain their relative order.

Why Insertion Sort matters in practice

Insertion Sort has properties that make it surprisingly practical:

Adaptive: O(n) when data is nearly sorted. If each element is at most k positions from its sorted position, it runs in O(nk).
Low overhead: No recursive calls, no auxiliary arrays, minimal bookkeeping.
Online: Can sort data as it arrives — you don’t need the full array upfront.

This is why hybrid algorithms use it:

TimSort (Python, Java) uses Insertion Sort for small runs
Introsort (C++ std::sort) switches to Insertion Sort for small partitions
Quick Sort implementations often switch to Insertion Sort when the subarray is below ~10 elements

Comparing the simple sorts

	Bubble Sort	Selection Sort	Insertion Sort
Best case	O(n)	O(n²)	O(n)
Average	O(n²)	O(n²)	O(n²)
Worst case	O(n²)	O(n²)	O(n²)
Stable	Yes	No	Yes
Adaptive	Yes (with flag)	No	Yes
Practical use	Almost none	Almost none	Small/nearly-sorted data

Insertion Sort is the clear winner among simple sorts for real-world use.

Practice problems

Sort an array using Insertion Sort
Insertion Sort on a linked list
Sort a nearly-sorted array where each element is at most k positions away
Count inversions in an array (each shift in Insertion Sort fixes one inversion)

Table of Contents