Sorting is a procedure in which the given elements are arranged in ascending or descending order. For example if the elements of an array are –
5, 11, 15, 8, 7, 54, 63, 44
After sorting these elements in ascending order, the elements would be –
5, 7, 8, 11, 15, 44, 54, 63
What is Insertion Sort is :
Insertion sort proceeds by inserting each element at the proper place in a sorted list. This is the same technique used by card players for arranging cards. When they receive a card, they place it in the appropriate place among the cards that they have already arranged.
We will consider our list to be divided into two parts – sorted and unsorted. Initially the sorted part contains only the first element of the list and unsorted part contains the rest of the elements. In each pass, the first element from the unsorted part is taken and inserted into the sorted part at appropriate place. If there are n elements in the list, then after n-1 passes the unsorted part disappears and our whole list becomes sorted. Let’s see the c program to sort an array using insertion sort.