Insertion sort

Take the next value and slide it left into its place among the values already sorted, like sorting cards in your hand.

Time O(n²)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Everything left of i is already sorted. Lift a[i] out as the key, shift every larger value one slot right, and drop the key into the gap.

Code

C++PythonC#

void insertionSort(vector<int>& a) {
    for (int i = 1; i < (int)a.size(); i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

def insertion_sort(a: list[int]) -> None:
    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
    # sorted in place

public static void InsertionSort(int[] a) {
    for (int i = 1; i < a.Length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

Tips

O(n) on nearly sorted data.
Stable and in place.

In the .NET library

The .NET sort switches to insertion sort for partitions of 16 elements or fewer, because it beats quick sort on tiny inputs.