Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
Straight Insertion Sort using C
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