Insertion Sort builds a sorted array one element at a time, much like sorting playing cards in a hand. It is efficient for small datasets and nearly sorted arrays where only a few shifts are needed.

It is not suitable for large inputs, but it remains worth understanding because of its simplicity, stability, and practical performance in hybrid algorithms.

This chapter covers how Insertion Sort works, how to implement it, and the scenarios where it outperforms more complex algorithms.

Insertion Sort builds a sorted portion of the array one element at a time. It picks the next unsorted element and inserts it into its correct position within the already-sorted region.

At any point during the algorithm, the array is divided into two regions:

The algorithm repeatedly takes the first element from the unsorted region and places it where it belongs in the sorted region, shifting larger elements to the right to make room.

The algorithm is straightforward: take each element, compare it to what is already sorted, and place it in the right position. No auxiliary data structures are required.

The algorithm has six steps:

The standard implementation shifts elements rather than swapping them. An alternative approach uses adjacent swaps, but shifting elements to the right in a single pass and then placing the key in its final position is more efficient: each shift is a single assignment, while a swap requires three assignments (using a temporary variable).

The inner while loop shifts elements to the right as long as they are greater than the key. It stops at the first element that is smaller than or equal to the key, and the key drops into the gap right after that element. Insertion Sort is stable because the loop shifts only elements that are strictly greater than the key, which preserves the original relative order of equal elements.

The outer loop picks each unsorted element starting from index 1. The inner while loop shifts larger elements to the right. After the loop, the key is placed into the correct position.

Adaptive: Yes. The running time depends on how "sorted" the input already is. If the input has very few inversions (pairs of elements that are out of order), Insertion Sort runs close to O(n). This adaptive property is what makes it valuable for nearly sorted data.

Stability

Insertion Sort is stable. The inner while loop's condition uses strict greater-than (arr[j] > key), so it never shifts an element that equals the key. A new equal element comes to rest just after the existing ones, which preserves their original relative order.

This stability is the reason hybrid algorithms like TimSort and Introsort fall back to Insertion Sort for small runs: they retain the overall sort's stability guarantee while exploiting Insertion Sort's low overhead on small inputs.

The following table shows comparisons for 10,000 elements in different scenarios:

The gap between best and worst case spans roughly four orders of magnitude. For nearly sorted data, Insertion Sort is competitive with O(n log n) algorithms. For random data, it is not.

Good Use Cases

Nearly sorted data. If the input is almost sorted with only a few elements out of place, Insertion Sort's adaptive nature makes it highly efficient. Each out-of-place element only needs a small number of shifts.

Small arrays. For arrays with fewer than 10-20 elements, the overhead of more complex algorithms like Merge Sort or Quick Sort (function call overhead, partitioning logic) makes them slower than Insertion Sort. The low constant factors of Insertion Sort give it an edge on small inputs.

Online sorting (sorting as data arrives). When elements arrive one at a time and the collection must stay sorted, Insertion Sort handles each arrival directly. Each new element is inserted into its correct position as it comes in.

As a subroutine in hybrid algorithms. Hybrid algorithms are the most common practical use case. Production sorting implementations use Insertion Sort as a building block:

When to Avoid

Large random datasets. With O(n^2) average-case complexity, Insertion Sort cannot compete with O(n log n) algorithms for large inputs. Sorting 1 million random elements with Insertion Sort takes roughly 250 billion comparisons on average (500 billion in the worst case), while Merge Sort needs about 20 million.

Performance-critical paths with unpredictable data. If the input is not guaranteed to be small or nearly sorted, use a general-purpose O(n log n) algorithm instead.

The following table summarizes the trade-offs: