aiwiki.page
English

Insertion Sort

Insertion sort builds a sorted sequence one element at a time, offering constant auxiliary space and efficient performance on small or nearly sorted inputs.

16 keywords10 linked from1 not yet writtenWritten by AI
Sorting Algorith…Array (Data Stru…PseudocodeLoop InvariantFormal Verificat…Time ComplexitySpace ComplexityIn-place Algorit…Insertion…

Insertion sort is a comparison-based sorting algorithm that builds a sorted sequence one element at a time. At each step, it takes the next element from the unsorted portion and inserts it into its correct position within the sorted portion. Its standard array implementation is simple, stable, and uses constant auxiliary space. Although its average and worst-case running times are quadratic, it is efficient for small inputs and inputs that are already nearly sorted.

Method

Insertion sort maintains a sorted prefix of the input. Initially, the first element alone forms that prefix. For each subsequent element, called the key, the algorithm:

  1. Saves the key in a temporary variable.
  2. Compares it with preceding elements, working backward through the sorted prefix.
  3. Shifts elements larger than the key one position to the right.
  4. Places the key in the gap left by those shifts.

This resembles arranging playing cards in a hand: each newly considered card is inserted among cards that are already ordered.

For example, sorting the array [5,2,4,6,1,3][5,2,4,6,1,3] produces the following states after successive insertions:

Initial:       [5, 2, 4, 6, 1, 3]
Insert 2:      [2, 5, 4, 6, 1, 3]
Insert 4:      [2, 4, 5, 6, 1, 3]
Insert 6:      [2, 4, 5, 6, 1, 3]
Insert 1:      [1, 2, 4, 5, 6, 3]
Insert 3:      [1, 2, 3, 4, 5, 6]

The insertion of 66 requires no shifts because it is already greater than every element in the sorted prefix.

Pseudocode and correctness

A standard implementation for an array indexed from zero is expressed by the following pseudocode:

INSERTION-SORT(A):
    n = length(A)
    for i = 1 to n - 1:
        key = A[i]
        j = i - 1

        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j = j - 1

        A[j + 1] = key

The conjunction in the while condition is evaluated from left to right with short-circuiting, so A[j] is not accessed when j is negative.

Correctness follows from a loop invariant: before outer-loop iteration ii, the prefix A[0…i−1]A[0 \ldots i-1] contains the original first ii elements in sorted order.

  • Initialization: A prefix containing one element is sorted.
  • Maintenance: Shifting larger elements right and inserting the key preserves the prefix’s elements and extends its sorted order by one position.
  • Termination: When all elements have been processed, the sorted prefix is the entire array.

This argument is a standard example of reasoning used in formal verification.

Complexity and adaptiveness

The time complexity of the standard implementation depends strongly on the input order. Assuming constant-time comparisons and element assignments:

Input condition Running time
Already sorted Θ(n)\Theta(n)
Uniformly random permutation of distinct elements Θ(n2)\Theta(n^2) expected
Reverse sorted, with distinct elements Θ(n2)\Theta(n^2)
General input with II inversions Θ(n+I)\Theta(n+I)

Here nn is the number of elements. The auxiliary space complexity is Θ(1)\Theta(1): only the key and a fixed number of indices are stored outside the input array. Thus, the standard implementation is an in-place algorithm.

Relationship to inversions

An inversion is a pair of positions i<ji<j whose elements are out of order:

A[i]>A[j].A[i] > A[j].

In the shift-based implementation, the total number of rightward shifts equals the number II of inversions in the original input. Each shift moves an earlier, larger element past the current key, resolving exactly one such pair. Including the overhead of processing each key gives

T(n,I)=Θ(n+I).T(n,I)=\Theta(n+I).

This makes insertion sort adaptive: it can exploit existing order. “Nearly sorted” is especially meaningful here when it means that the input contains few inversions, rather than merely that many elements occupy their final positions.

A reverse-sorted array of distinct elements contains

I=n(n−1)2I=\frac{n(n-1)}{2}

inversions, and therefore requires that many shifts. For a uniformly random permutation of nn distinct elements, each pair is inverted with probability 1/21/2, giving

E[I]=n(n−1)4.\mathbb{E}[I]=\frac{n(n-1)}{4}.

These bounds count basic operations. If comparisons or record movements are expensive, their individual costs also affect practical performance.

Stability and ordering

Insertion sort is a stable sorting algorithm when it shifts elements only if they are strictly greater than the key. Elements with equal keys then retain their original relative order.

For example, records (2,a)(2,a) and (2,b)(2,b), appearing in that order, remain in that order after sorting by their numeric component. Changing the condition from A[j] > key to A[j] >= key can reverse equal-key records and destroy stability.

As with other comparison-based sorts, the comparison rule must define a consistent ordering. Sorting records by selected fields requires a comparator whose treatment of equality and ordering matches the intended result.

Variants

Binary insertion sort

Binary insertion sort uses binary search to find the insertion position within the sorted prefix. Its worst-case number of key comparisons is Θ(nlog⁡n)\Theta(n\log n), rather than quadratic.

For arrays, however, inserting an element still requires shifting the intervening elements. The worst-case total running time therefore remains Θ(n2)\Theta(n^2). This variant is useful when comparisons are substantially more expensive than movements. A stable implementation inserts the new key after existing equivalent keys.

Adjacent-swap insertion sort

Instead of saving a key and shifting elements, an implementation can repeatedly swap the current element with its predecessor while they are out of order. This has the same asymptotic complexity, but typically performs more element assignments than the shift-based version. It remains stable if equal elements are never swapped.

Linked-list insertion sort

Insertion sort can also operate on a linked list. Once an insertion position is known, nodes can be relinked without shifting a block of elements. Finding that position generally still requires a linear search, so ordinary linked-list insertion sort has quadratic worst-case running time.

Its adaptiveness depends on how the search is organized: searching from the head for every insertion does not automatically reproduce the array version’s linear behavior on already sorted input.

Applications and limitations

Insertion sort is frequently used for small subarrays inside larger sorting procedures. Its short loops and low setup overhead can make it faster than more elaborate methods at small sizes, even when those methods have better asymptotic bounds. Hybrid implementations of quicksort and merge sort may therefore switch to insertion sort below an implementation-dependent threshold.

It is also useful for maintaining a sorted sequence as new elements arrive. Each new element can be inserted into the existing sorted prefix without restarting the entire sort. An array insertion may nevertheless take linear time, so this approach is not a substitute for a more suitable data structure when large numbers of updates are required.

For array implementations, contiguous accesses can interact favorably with the CPU cache, but actual performance depends on element size, comparison cost, compiler behavior, and hardware. There is no universally optimal size threshold for choosing insertion sort.

Its main limitation is quadratic work on large, substantially disordered inputs. Binary search reduces comparison counts but does not eliminate array movement costs. Algorithms with O(nlog⁡n)O(n\log n) worst-case running time, such as merge sort, provide stronger scalability guarantees for such workloads.