# Insertion Sort in C & C++ – Program & Algorithm

In this tutorial I will explain about algorithm for insertion sort in C and C++ using program example. The insertion sort inserts each element in proper place. The strategy behind the insertion sort is similar to the process of sorting a pack of cards. You can take a card, move it to its location in sequence and move the remaining cards left or right as needed.

In insertion sort, we assume that first element A in pass 1 is already sorted. In pass 2 the next second element A is compared with the first one and inserted into its proper place either before or after the first element. In pass 3 the third element A is inserted into its proper place and so on.

## Algorithm for Insertion Sort in C & C++

Let ARR is an array with N elements
2. Repeat step 3 to 8 for I=1 to N-1
3. Set Temp=ARR[I]
4. Set J=I-1
5. Repeat step 6 and 7 while Temp<ARR[J] AND J>=0
6. Set ARR[J+1]=ARR[J] [Moves element forward]
7. Set J=J-1
[End of step 5 inner
loop]
8. Set ARR[J+1]=Temp [Insert element in proper place]
[End of step 2 outer
loop]
9. Exit

## Program for Insertion Sort in C++ ## Complexity of Insertion Sort in C & C++

There is 1 comparison during pass 1 for proper place. There are 2 comparisons during pass 2 for proper place. There are 3 comparisons during pass 3 for proper place, and so on accordingly.

F(n) = 1 + 2 + 3 + . . . . + (n-1) = n (n-1)/2 = O(n2)

Hence complexity for insertion sort program in C and C++ is O(n2).

### 23 thoughts on “Insertion Sort in C & C++ – Program & Algorithm”

1. 1. thank you! It helps me a lot!

2. it’s gud ,but you have to explain more

3. THANKS A LOT !!!!!!! IT HELPS ME VERY MUCH

4. 1. duplicates values are not allowed.
2.if you enter array size greater than current size of an array it display a message that you enter large size array and again we have to choose the size unless we have chose right.
suppose you decleare an array a and you chose array size 13 it is an error .

1. Vijay Kumar Sharma

you can store the array size dynamically.

1. You mean I have to create a heap to store the sorted elements ?

5. guatam prajapati

sorry i didnt say anything because i have fever and headche

6. How floating number sorted in insertion sort algorithm. …????

7. Vijay Kumar Sharma

Please describe the best case algo

8. thanks it helps me.

9. why is not working?

1. because its not in the mood to work

10. from the sorted list is not working?

11. it says cant build project (i use code blocks)

12. how to print each iteration?

13. Sakhawat Akib

Bro, I need merge sort also..

14. can we write a[i]=a[j]; inside the while loop instead of a[j+1]=a[j];
if not ? why,,,,

15. I have an error at (i=0;i<n;i++)
The last part

16. Why there is j=j-1?

17. could you please implement Insertion Sort and Merge Sort in a single source file. You are required to note the time Merge Sort and Insertion Sort takes. Actually this is my assignment. I’ll be very thankful to you.

18. ...............

How to specify space between the elements