Insertion Sort

Insertion sort builds a sorted prefix one element at a time; O(n^2) overall but fast on small or nearly sorted arrays.

One card at a time

Insertion sort works the way many people sort a hand of cards: keep a sorted prefix and, for each new element, slide it left past larger elements until it sits in the right place. After processing k elements the first k are sorted; when all n are processed the array is sorted.

Cost and its best case

In the worst case, a reverse-sorted array, each element shifts all the way to the front, giving O(n^2). But if the array is already nearly sorted, each element moves only a little, and the cost approaches O(n). This adaptivity to existing order is what sets insertion sort apart from other quadratic sorts.

• Best case (nearly sorted): O(n)
• Average and worst case: O(n^2)
• Extra space: O(1); stable: yes
• Online: can sort elements as they arrive

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = key

Counting inversions

Insertion sort's shift count equals the number of inversions in the input, the pairs that are out of order. This is why nearly sorted data, which has few inversions, is handled quickly, and it makes insertion sort a natural way to reason about how disordered an array is. A binary search can locate each insertion point in O(log n), but the shifting still costs O(n) per element, so the overall bound does not improve.

Where it is genuinely useful

Because of low overhead and excellent behaviour on short or nearly ordered inputs, insertion sort is used as the base case inside fast recursive sorts. Production quicksort and merge sort implementations switch to insertion sort once a subarray drops below a small threshold, since it beats the recursive machinery on tiny inputs. It is also a good online sort, keeping a stream sorted as each new element arrives.