Ідея: будуємо відсортований префікс. На кроці i просуваємо елемент вліво, обмінюючи сусідні пари a[j-1] і a[j], поки порядок не стане правильним.
Інваріант: перед початком ітерації i префікс [0..i-1] відсортований.

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