C program for Insertion Sort. **Insertion sort** is one of the **simple-stable-in place** Sorting Algorithm which is efficient when applied over small set of data. While insertion sort takes more time to perform sorting over large list **i.e less efficient for large set of data**, as compare to other sorting algorithm. Insertion sort reminds one of **Selection sort**. You can also see other sorting algorithm implementation like, Heap sort, bubble sort etc.

**Insertion sort:**

How will you** sort your mark-sheet arranged in pile**, according to marks obtained? Well very easy, a very practical approach is to first, compare first and second marks and put them in **order or correct position by inserting**, now take out third one and compare it with second and first and put it in right position. Now take out fourth and so on. This approach of inserting element in a sorted list is called as **Insertion sort**. Here is **Pseudocode:**

### Pseudocode** **for insertion sort algorithm:

for i <- 1 to n-1 (A[0....n]) Elem <- A[i] j <- i-1 while j > 0 && A[j-1] > Elem A[j] <- A[j-1] j <- j-1 A[j] <- x

## C program for Insertion Sort

#include <stdio.h> //Insertion Sort function to Sort Integer array list int *insertionSort(int array[],int n) { int j,temp,i; //Iterate start from second element for (i = 1; i < n; i++) { j = i; //Iterate and compare till it satisfies condition while ( j > 0 && array[j] < array[j-1]) { //Swaping operation temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; j--; } } //return Sorted array return array; } int main() { //declaring variables int array[1000],n,i; //Number of elements in array form user input printf("Enter the number of element you want to Sort : "); scanf("%d",&n); //code to ask to enter elements from user equal to n printf("Enter Elements in the list : "); for(i = 0; i < n; i++) { scanf("%d",&array[i]); } //calling insertionSort function defined above and gettting //sorted array in sortArray variable int *sortArray = insertionSort(array,n); //print sorted array for(i = 0; i < n; i++ ) { printf("%d\t",sortArray[i]); } }

### Output of C program for Insertion Sort:

### Example of Insertion sort:

Still getting problem or confused how insertion sort algorithm works, then see the images below, demonstrating the operation performed to sort the array:

Let us take integer array **A = 18,9,5,12,1**

Hope this example is helpful. Do comment below with your experience, problem or code. Your comment is very valuable to us.