Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. More details can be found here at https://en.wikipedia.org/wiki/Insertion_sort

Let’s say we have an array a, so at each i-th pass, a[i] is successively compared with a[i-1], a[i-2], etc. until an element smaller than a[i] is found or the beginning of the array is reached. Elements that are found to be greater than a[i], are moved right by one position each to make room for a[i].

The time complexity of this algorithm is O(n^2).

The complete source code is given below

/*
* File:   StraightInsertionSort.c
* Author: https://www.roytuts.com
*/

#include <stdio.h>
#include <stdlib.h>

void straightInsertionSort(int a[], int n) {
int i = 1, j, k = 0;
int temp;
while (i < n) {
j = i - 1;
temp = a[j + 1];
k = i;
while (j >= 0) {
if (temp < a[j]) {
k = j;
j--;
} else {
break;
}
}
j = i;
while (j > k) {
a[j] = a[j - 1];
j--;
}
a[j] = temp;
i++;
}
printf("\n");
printf("\nThe sorted array elements are given below\n");
for (i = 0; i < n; i++) {
printf("a[%d]=%d ", i, a[i]);
}
}

int main() {
int i, n = 6;
int a[] = {15, 8, 17, 12, 38, 19};
printf("\n:: Straight Insertion Sort ::\n");
printf("\nInput array elements\n");
for (i = 0; i < n; i++) {
printf("a[%d]=%d ", i, a[i]);
}
straightInsertionSort(a, n);
}

Output

:: Straight Insertion Sort ::

Input array elements
a=15 a=8 a=17 a=12 a=38 a=19

The sorted array elements are given below
a=8 a=12 a=15 a=17 a=19 a=38