挿入ソートは、配列の整列済みの部分に、新たな要素を適切な位置に挿入することで整列を行うアルゴリズムである。アルゴリズムとして、整形済みの部分の右側に新しい要素を挿入する。次に、挿入した要素の値とその左の要素の値を比較して、左の値が大きければ、左右の値を入れ替える。値の入れ替えを行なったとに、もう一度、左の要素の値と比較して、必要に応じて左右の値の入れ替えを行う。この操作を左右の入れ替えがなくなるまで、あるいは整形済み部分の先頭に達するまで行う。

1. A[1] から A[i] までが整列済みとする。A[i + 1] を部分配列 A[1..i] に挿入する。
   1. j = i として、A[j] と A[j + 1] を比較して、A[j] > A[j + 1] ならば、両者の値を入れ換える。
   2. j = i, i - 1, ..., 3, 2 と j の値を 1 ずつ減らしなら、A[j] と A[j + 1] を比較する。入れ替えが起こらなくなったら（つまり、A[j] < A[j + 1] に達したたら）、A[i + 1] の並べ替えが完了する。
2. i = 1, 2, ..., n に対して手順 1 を繰り返す。

挿入ソートの探索回数は、n 個の要素を持つ配列に対して i 回目の探索において、A[i], A[i + 1], ..., A[n] の中から最小値を探索し、その最小値を A[1], A[2], ..., A[i-1] と比べながら値の入れ替えを行なっている。n 個の要素を持つ配列に対して i = 2, 3, ..., n として同様な操作を繰り返すので、最小値探索は n + (n-1) + ... + 3 + 2 = n(n+1)/2 - 1 回行われ、値の比較と入れ替えは (n-1) + (n-2) + ... + 3 + 2 = n(n-1)/2 回行われる。そのため、挿入ソートの計算量は O(n²) となる。

挿入ソートは、ランダムな並び順の配列を整列したり、あるいは昇順の配列を降順に並べ替えるときには適していない。しかし、整列済みの配列に新しい要素を追加するときに、効率が良い。

#include <stdio.h>

void insertionSort (int array[], int array_size) {
    int i, j, k;

    for (i = 1; i < array_size; i++) {
        k = array[i];
        j = i - 1;

        while ((j >= 0) && (array[j] > k)) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = k;
    }

}


int main (void) {

    int i;
    int array[10] = {3, 6, 1, 7, 2, 0, 4, 5, 9, 8};

    printf("       array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    insertionSort(array, sizeof(array) / sizeof(array[0]));

    printf("sorted array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}