Implement insertion sort.
#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.