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). Continue reading “Straight Insertion Sort using C”