☕ Buy me a coffee — $3

Insertion Sort

Overview

Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time. It works similarly to how you might sort playing cards in your hands - you pick up one card and insert it into its correct position among the cards you're already holding.

The algorithm maintains a sorted subarray at the beginning of the array and repeatedly takes the next element from the unsorted portion and inserts it into the correct position in the sorted portion.

Of the elementary O(n²) sorts, insertion sort is the one that has genuine standing in modern production code. Every high-performance general-purpose sort in the standard libraries of Python, Java, Rust, Go and C++ uses insertion sort internally, not as the main algorithm, but as the base case that a divide-and-conquer sort falls back to when the subarray gets small enough. That is not a nostalgic homage. It is because insertion sort beats mergesort, quicksort and heapsort on real hardware for arrays below roughly 16–64 elements, and the recursive sorts are structured to hand off their tiniest partitions to insertion sort for exactly that reason.

History and Why It Matters

Insertion sort is the algorithm you invent when you sort a hand of playing cards: you pick up cards one at a time and slide each into its correct position among the cards you are already holding. That physical model, older than computing itself, has shaped how the algorithm has been described for as long as there has been a literature about it. John Mauchly discussed it in a 1946 lecture on machine methods for sorting, and it appears in Knuth's The Art of Computer Programming, Volume 3 (1973) as the first sorting method presented in detail, because, Knuth notes, it is the one that arises most naturally from the way people sort.

Its persistent role in modern systems traces back to a specific observation, refined and tested over decades: on small arrays, insertion sort is faster than every O(n log n) sort ever written. Robert Sedgewick's PhD thesis (1975) on quicksort established the practice of switching to insertion sort for subarrays below a threshold (Sedgewick's original suggestion was around 10); Java's Arrays.sort switches at 47 elements; CPython's Timsort uses a run length of 32–64. The reason is that O-notation hides constants, and insertion sort has some of the smallest constants of any sort ever devised, a single comparison, a single swap, and no recursion, function calls, or extra memory.

The theoretical foundation for its use is a result sometimes credited to Yao (1980) but known informally earlier: for arrays of at most k elements, the crossover point at which a comparison-based recursive sort beats a simple quadratic sort depends on the ratio of the recursive constant to the quadratic constant. On real machines that ratio is roughly 16 for quicksort/insertion sort and about 32 for mergesort/insertion sort, which is why those particular thresholds appear in real implementations.

How It Works

The algorithm works by:

  1. Starting with the second element (index 1) as the key
  2. Comparing the key with elements in the sorted subarray to its left
  3. Shifting elements greater than the key one position to the right
  4. Inserting the key into its correct position
  5. Repeating for all remaining elements

Algorithm


InsertionSort(arr):
    n = length of arr
    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

Implementation


def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        
        # Move elements greater than key one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr

Complexity Analysis

  • Time Complexity:
    • Best Case: O(n) - when array is already sorted
    • Average Case: O(n²)
    • Worst Case: O(n²) - when array is sorted in reverse order
  • Space Complexity: O(1) - only uses a constant amount of extra space

Insertion Sort is efficient for small datasets and nearly sorted arrays. It's adaptive and stable, making it useful in practice despite its O(n²) worst-case complexity.

Characteristics

  • Stable: Yes - equal elements maintain their relative order
  • In-place: Yes - only requires O(1) extra space
  • Adaptive: Yes - efficient for nearly sorted arrays
  • Online: Yes - can sort a list as it receives it

Why It Is Fast on Nearly-Sorted Data

Insertion sort's adaptivity is not just a minor optimisation, it is one of the most consequential properties any sorting algorithm can have. On an input that is already sorted, the inner while loop's condition arr[j] > key is false on the very first iteration, and the algorithm degenerates to a single pass through the outer loop that reads each element and moves on. That is n−1 comparisons and zero moves, strictly O(n).

On an input that is "almost sorted", formally, where each element is at most a bounded distance k from its final position, insertion sort runs in O(kn). For k as large as the square root of n, that is still o(n log n), which means insertion sort beats the theoretically optimal O(n log n) sorts on inputs that are close enough to sorted. Real-world datasets are frequently in this state: partially-sorted log entries, streams that were sorted but have had a few late arrivals inserted, files that were sorted and then had a small edit made in the middle. These are exactly the inputs on which insertion sort quietly dominates.

Timsort, the hybrid sort that ships as Python's default and Java's default for object arrays, is built around this observation. It scans the input for existing "runs" of sorted elements and extends short runs to a minimum length using insertion sort, then merges the resulting long runs. On real-world data, which is almost never uniformly random, this strategy is meaningfully faster than a pure O(n log n) sort. Insertion sort's adaptivity is the mathematical foundation that makes the whole Timsort architecture work.

The "Online" Property

Insertion sort is one of very few sorting algorithms that is online: you can feed it elements one at a time, and the sorted prefix is always correct with respect to the elements seen so far. Every other elementary sort, and every O(n log n) sort, requires the complete input in memory before it can produce any output.

This property makes insertion sort the natural choice for maintaining a sorted list as new elements arrive incrementally, a use case that is more common in real systems than theoretical treatments suggest. A game engine that needs to keep visible objects sorted by depth as new objects enter the scene, a database index buffer that accumulates recent inserts before flushing to disk, or a leaderboard that receives score submissions in real time: all of these are natural fits for insertion sort's "sort-as-you-go" mechanic. In each case the alternative, re-sorting the whole list on every insertion, is much slower even with an asymptotically better algorithm.

Variants and Related Algorithms

Binary Insertion Sort

The plain algorithm searches for the insertion position by linear scan through the sorted prefix. If the prefix is sorted, we could locate the position in O(log k) time using binary search. That yields binary insertion sort, with O(n log n) comparisons in total. This sounds like a strict improvement, but it is not: the number of moves is unchanged at O(n²), and moves dominate the running time on most hardware. Binary insertion sort is faster in settings where comparisons are expensive (comparing long strings, for example) and moves are cheap; on integer arrays it is not obviously better than the linear version. It shows up in some Timsort implementations as the base-case sort for exactly this reason: when Timsort is comparing complex user-defined objects, saving comparisons matters.

Shellsort

Donald Shell's 1959 algorithm generalises insertion sort by first sorting elements that are far apart, then progressively closer together, ending with a plain gap-1 pass (which is ordinary insertion sort). The intuition is that insertion sort's slowness comes from small elements at the end of the array having to travel a long distance one step at a time; by first ensuring the array is "sorted at gap h" for a large h, subsequent gap-1 passes have much less work to do. The empirical complexity of Shellsort with good gap sequences (Ciura's or Sedgewick's) is around O(n4/3), solidly better than O(n²), and Shellsort remains competitive with more sophisticated sorts on arrays in the low thousands.

Library Sort

A theoretical variant that leaves gaps in the sorted array to reduce the amortised move cost of each insertion, achieving O(n log n) expected time. Library sort is intellectually interesting but has never displaced conventional sorts in practice because its constants and memory overhead are unfavourable.

Common Misconceptions

  • "Insertion sort's inner loop is a swap." A common but slower implementation performs a full swap of the key with each larger element it passes. The standard implementation instead shifts each larger element one position to the right and only writes the key once, at the end. The shift version does about half the memory writes of the swap version and is meaningfully faster in practice. This is the version shown above.
  • "Insertion sort is only useful for tiny arrays." The primary role of insertion sort in modern code is exactly that, the base case of hybrid sorts, but it is also the right choice for streaming or online workloads regardless of size, and for nearly-sorted inputs it is genuinely competitive with O(n log n) sorts up into the tens of thousands.
  • "Because it is O(n²), insertion sort must be worse than heapsort." On uniform random data, yes. On real data, which is very often partially sorted or has structure, insertion sort's adaptivity often wins even at surprising sizes. Timsort's design decisions all follow from this observation. Never assume the asymptotic winner is the practical winner without measuring on your actual data.

When to Use Insertion Sort

Insertion sort is one of the elementary sorts that has kept its place in serious code, for specific well-understood reasons. It is the right choice when:

  • The array is small, typically under about 32 elements. Below this size no O(n log n) sort can match its speed on typical hardware, which is why every production sort uses it as a base case.
  • The array is nearly sorted, a small number of elements out of place, or a mostly-sorted array with recent additions appended at the end. Its adaptive behaviour makes it O(n) in the ideal case and O(kn) in general, often faster than any general-purpose sort.
  • The elements arrive incrementally and you need the collection to remain sorted after each arrival. This is the "online" use case, where alternatives require re-sorting from scratch on each update.
  • You need a stable, in-place sort with a very small code footprint. On embedded systems where program size is constrained, insertion sort's implementation compiles to a handful of instructions, substantially smaller than a general-purpose library sort.
  • You are writing a hybrid sort. Almost any recursive sort benefits from cutting off at a small base case and switching to insertion sort there. This is the single most common performance optimisation applied to production sorting implementations.

Avoid insertion sort when the input is large and uniformly random with no expected structure, a general-purpose O(n log n) sort will be several orders of magnitude faster at n = 105 and above. In that regime, use quicksort, mergesort, or Timsort.

Example

Sorting [12, 11, 13, 5, 6]: 

Initial: [12, 11, 13, 5, 6]
Pass 1:  [11, 12, 13, 5, 6]  (insert 11 before 12)
Pass 2:  [11, 12, 13, 5, 6]  (13 is already in place)
Pass 3:  [5, 11, 12, 13, 6]  (insert 5 at beginning)
Pass 4:  [5, 6, 11, 12, 13]  (insert 6 after 5)
Sorted:  [5, 6, 11, 12, 13]

Related Algorithms

Explore other sorting algorithms: