Insertion Sort — Why It Is Fast on Small and Nearly Sorted Data

How Insertion Sort Works

Insertion Sort builds the sorted array one element at a time. It takes each element from the unsorted portion and inserts it into the correct position within the sorted portion, shifting existing elements as needed.

The Algorithm

for i = 1 to n-1:
  key = arr[i]
  j = i - 1
  while j >= 0 and arr[j] > key:
    arr[j+1] = arr[j]
    j = j - 1
  arr[j+1] = key

Why Insertion Sort Is Special

Unlike Bubble Sort and Selection Sort, Insertion Sort has a genuinely useful best case:

Case	Comparisons	Shifts
Best (sorted)	n - 1	0
Nearly sorted	~ n + d	~ d
Average	n²/4	n²/4
Worst (reversed)	n²/2	n²/2

Where d is the number of inversions (pairs of elements in wrong order). For nearly sorted data, d is small, making Insertion Sort run in nearly O(n) time.

Adaptive Behavior

Insertion Sort is adaptive — its running time depends on how sorted the input already is. This makes it ideal for:

• Online sorting: elements arrive one at a time
• Nearly sorted data: only a few elements are out of place
• Small arrays: the overhead of more complex algorithms (like Quick Sort's recursion) exceeds the benefit

Used in Production Algorithms

Real-world sorting implementations use Insertion Sort as a building block:

• Timsort (Python, Java): Uses Insertion Sort for runs shorter than 64 elements
• Introsort (C++ STL): Switches from Quick Sort to Insertion Sort when partition size drops below 16
• V8 (JavaScript): Uses Insertion Sort for arrays with fewer than 10 elements

Stability

Insertion Sort is stable — elements with equal keys maintain their original relative order, because the algorithm only shifts elements that are strictly greater.