Insertion Sort - Code

Here is the implementation of insertion sort:

function insertionSort(arr):
    n = arr.length
    for i from 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

Time: $O(n^2)$ worst case (reverse sorted). $O(n)$ best case (already sorted).

Space: $O(1)$. Only a few variables for indices (except for the input array itself).

Stability: Stable. Equal elements never swap past each other.

Insertion sort works well on nearly-sorted data and small arrays. Many library sorts use insertion sort for subarrays below a threshold (often $10$-$20$ elements).