Bentley insertion sort

insertion_sort.c

#include <stdbool.h>
#include <math.h>

// https://godbolt.org/z/eE853h

void swap(int a[], size_t i, size_t j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

void insertion_sort(int a[], size_t n) {
    for (size_t i = 1; i < n; i++) {
        for (size_t j = i; j > 0 && a[j-1] > a[j]; j--) {
            swap(a, j-1, j);
        }
    }
}

// Inline swap call
void insertion_sort2(int a[], size_t n) {
    for (size_t i = 1; i < n; i++)
        for (size_t j = i; j > 0 && a[j-1] > a[j]; j--) {
            int t = a[j];
            a[j] = a[j-1];
            a[j-1] = t;
        }
}

// Loop invariant code motion
void insertion_sort3(int a[], size_t n) {
    for (size_t i = 1; i < n; i++) {
        int t = a[i];
        size_t j = i;
        for (; j > 0 && a[j-1] > a[j]; j--) {
            a[j] = a[j-1];
        }
        a[j] = t;
    }