</>EmbeddedInterview

Implement insertion sort.

Easy"Coding: Sorting & Array Problems"
#include <stddef.h>

void insertion_sort(int *a, size_t n)
{
    for (size_t i = 1; i < n; i++) {
        int key = a[i];
        size_t j = i;
        while (j > 0 && a[j - 1] > key) {   /* shift larger elements right */
            a[j] = a[j - 1];
            j--;
        }
        a[j] = key;
    }
}

Points: O(n²) worst/average, O(n) on nearly sorted data, stable, in place, very small code: the best choice for small arrays (< ~20 elements) and data arriving almost sorted (e.g. keeping a short list of readings in order). Library sorts switch to insertion sort for small partitions.