Insertion Sort: Complete Guide with Examples
Insertion sort is one of the most intuitive sorting algorithms, mirroring how most people naturally sort playing cards. When you pick up cards one at a time, you don't restart the sorting process...
Key Insights
- Insertion sort achieves O(n) performance on nearly-sorted data, making it the optimal choice for maintaining sorted order as new elements arrive or for finishing partially-sorted arrays from other algorithms.
- The algorithm’s O(1) space complexity and stability make it invaluable in memory-constrained environments and when preserving the relative order of equal elements matters.
- Production sorting implementations like Timsort (Python, Java) and Introsort (C++) use insertion sort as a finishing step for small subarrays, proving its practical value beyond academic exercises.
Introduction to Insertion Sort
Insertion sort is one of the most intuitive sorting algorithms, mirroring how most people naturally sort playing cards. When you pick up cards one at a time, you don’t restart the sorting process with each new card—you find the right spot and slide it in. That’s insertion sort.
The algorithm builds a sorted portion of the array one element at a time. It takes each unsorted element and inserts it into its correct position within the already-sorted section. This approach makes it remarkably efficient for certain scenarios while being impractical for others.
Understanding insertion sort deeply isn’t just academic. It’s a building block for more sophisticated algorithms and remains the go-to choice in specific real-world situations that we’ll explore throughout this guide.
How Insertion Sort Works
The algorithm divides the array into sorted and unsorted regions. Initially, the sorted region contains just the first element (a single element is trivially sorted). We then iterate through the unsorted region, taking each element and inserting it into its correct position in the sorted region.
Here’s the process for each element:
- Store the current element as the “key”
- Compare the key with elements in the sorted region, moving from right to left
- Shift elements greater than the key one position to the right
- Insert the key into the gap created
def insertion_sort(arr):
"""
Sort array in-place using insertion sort.
Returns the same array reference, now sorted.
"""
for i in range(1, len(arr)):
key = arr[i] # Element to be inserted
j = i - 1 # Start comparing with element just before key
# Shift elements greater than key to the right
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # Shift element right
j -= 1
# Insert key into its correct position
arr[j + 1] = key
return arr
# Example usage
data = [64, 34, 25, 12, 22, 11, 90]
print(insertion_sort(data)) # [11, 12, 22, 25, 34, 64, 90]
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i - 1;
// Move elements greater than key one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
The key insight is that we’re not swapping elements—we’re shifting them. This distinction matters for performance and is why insertion sort outperforms bubble sort despite both being O(n²).
Time and Space Complexity Analysis
Insertion sort’s complexity varies dramatically based on input characteristics:
Best Case: O(n) — When the array is already sorted, each element requires only one comparison. The inner while loop never executes, giving us linear time.
Worst Case: O(n²) — When the array is reverse-sorted, each element must be compared with all previously sorted elements, resulting in 1 + 2 + 3 + … + (n-1) = n(n-1)/2 comparisons.
Average Case: O(n²) — Random data requires approximately half the maximum comparisons on average.
Space Complexity: O(1) — Insertion sort is in-place, requiring only a constant amount of additional memory regardless of input size.
Let’s instrument the algorithm to see these differences:
def insertion_sort_instrumented(arr):
"""
Insertion sort with operation counting for analysis.
"""
comparisons = 0
shifts = 0
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0:
comparisons += 1
if arr[j] > key:
arr[j + 1] = arr[j]
shifts += 1
j -= 1
else:
break
arr[j + 1] = key
return arr, comparisons, shifts
# Test different scenarios
import random
n = 100
# Best case: already sorted
sorted_arr = list(range(n))
_, comp, shifts = insertion_sort_instrumented(sorted_arr.copy())
print(f"Sorted array: {comp} comparisons, {shifts} shifts")
# Worst case: reverse sorted
reverse_arr = list(range(n, 0, -1))
_, comp, shifts = insertion_sort_instrumented(reverse_arr.copy())
print(f"Reverse array: {comp} comparisons, {shifts} shifts")
# Average case: random
random_arr = random.sample(range(n), n)
_, comp, shifts = insertion_sort_instrumented(random_arr.copy())
print(f"Random array: {comp} comparisons, {shifts} shifts")
# Output example:
# Sorted array: 99 comparisons, 0 shifts
# Reverse array: 4950 comparisons, 4950 shifts
# Random array: ~2500 comparisons, ~2500 shifts
Compared to other O(n²) algorithms: insertion sort typically outperforms bubble sort (fewer swaps) and selection sort (adaptive to input). Selection sort always performs O(n²) comparisons regardless of input order.
When to Use Insertion Sort
Use insertion sort when:
-
Data is nearly sorted — If elements are at most k positions from their sorted position, complexity drops to O(nk). This happens frequently with log files, time-series data, or incrementally updated datasets.
-
Dataset is small — For arrays under 10-50 elements, insertion sort often beats “faster” algorithms due to lower overhead. No recursion, no auxiliary arrays, no complex partitioning.
-
Online sorting is required — When data arrives one element at a time and must remain sorted, insertion sort naturally handles this. Each insertion is O(n), which is optimal for maintaining a sorted list.
-
Stability matters — Insertion sort is stable (equal elements maintain their relative order). This is crucial when sorting by multiple keys sequentially.
-
Memory is constrained — The O(1) space requirement makes it suitable for embedded systems or when working with memory-mapped files.
Avoid insertion sort when:
- Dataset is large and randomly ordered
- You need guaranteed O(n log n) performance
- Data is stored in a structure with expensive element access (like a singly-linked list traversed from the head)
Variations and Optimizations
Binary Insertion Sort
The standard algorithm uses linear search to find the insertion point. Since the left portion is already sorted, we can use binary search to reduce comparisons from O(n) to O(log n) per element. However, we still need O(n) shifts, so overall complexity remains O(n²):
import bisect
def binary_insertion_sort(arr):
"""
Insertion sort using binary search to find insertion point.
Reduces comparisons but not overall complexity.
"""
for i in range(1, len(arr)):
key = arr[i]
# Binary search for insertion point in sorted portion
insertion_point = bisect.bisect_left(arr, key, 0, i)
# Shift elements and insert
# This is equivalent to: arr.insert(insertion_point, arr.pop(i))
# But we do it in-place for clarity
for j in range(i, insertion_point, -1):
arr[j] = arr[j - 1]
arr[insertion_point] = key
return arr
This optimization shines when comparisons are expensive (complex objects, string comparisons) but element moves are cheap.
Shell Sort Extension
Shell sort generalizes insertion sort by comparing elements separated by a gap, progressively reducing the gap until it becomes 1 (standard insertion sort). This allows elements to move to their approximate position quickly:
def shell_sort(arr):
"""
Shell sort: insertion sort with diminishing gaps.
Achieves better than O(n²) for most gap sequences.
"""
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
key = arr[i]
j = i
while j >= gap and arr[j - gap] > key:
arr[j] = arr[j - gap]
j -= gap
arr[j] = key
gap //= 2
return arr
Practical Implementation Examples
Sorting Objects by Property
from dataclasses import dataclass
from typing import List, Callable, Any
@dataclass
class Task:
name: str
priority: int
created_at: float
def insertion_sort_by(arr: List[Any], key: Callable) -> List[Any]:
"""
Generic insertion sort with key function for custom ordering.
"""
for i in range(1, len(arr)):
current = arr[i]
current_key = key(current)
j = i - 1
while j >= 0 and key(arr[j]) > current_key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = current
return arr
# Sort tasks by priority
tasks = [
Task("Deploy", 2, 1000),
Task("Hotfix", 1, 1001),
Task("Refactor", 3, 999),
]
sorted_tasks = insertion_sort_by(tasks, key=lambda t: t.priority)
Hybrid Quicksort with Insertion Sort
Production implementations switch to insertion sort for small subarrays:
def hybrid_quicksort(arr, low=0, high=None, threshold=16):
"""
Quicksort that switches to insertion sort for small subarrays.
This is how real-world sorting implementations work.
"""
if high is None:
high = len(arr) - 1
if high - low < threshold:
# Use insertion sort for small subarrays
for i in range(low + 1, high + 1):
key = arr[i]
j = i - 1
while j >= low and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Standard quicksort partitioning
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
pivot_pos = i + 1
hybrid_quicksort(arr, low, pivot_pos - 1, threshold)
hybrid_quicksort(arr, pivot_pos + 1, high, threshold)
return arr
The threshold of 16 is common in practice—small enough that insertion sort’s O(n²) doesn’t hurt, large enough to avoid quicksort’s recursion overhead.
Conclusion
Insertion sort occupies a specific niche in the sorting algorithm landscape. It’s not the fastest general-purpose algorithm, but it excels in scenarios that play to its strengths: small datasets, nearly-sorted data, streaming input, and memory-constrained environments.
The algorithm’s simplicity makes it easy to implement correctly, modify for custom requirements, and reason about. Its use in hybrid sorting algorithms demonstrates that even “slow” algorithms have their place in production systems.
When choosing a sorting algorithm, consider your data characteristics. If you’re maintaining a sorted list with occasional insertions, insertion sort is optimal. If you’re sorting large random datasets, look to merge sort or quicksort. Understanding when each tool fits is what separates competent engineers from those who just memorize Big-O notation.