Link copied to clipboard. Share away!

Dismiss

Published on 12 Mar 2020

In this article, we will be **discussing Insertion sort in C, C++, Java with examples, complete algorithm, and time complexity calculation**.

Prerequisites:Bubble Sort, Selection Sort

Insertion sort is slightly different from the other sorting algorithms. It is based on the idea that each element in the array is consumed in each iteration to find its right position in the sorted array such that the entire array is sorted at the end of all the iterations.

In other words,**it compares the current element with the elements on the left-hand side (sorted array)**.If the current element is greater than all the elements on its left hand side, then it leaves the element in its place and moves on to the next element. Else it finds its correct position and moves it to that position by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead.

Conclusion: Each iteration of insertion sort causes the sorted subset to grow, and the unsorted subset to shrink.

Let us consider an array with 5 elements, A = [7, 1, 23, 4, 19]. **Below is how insertion sort works for this array**.

Here is the pseudocode implementation of Insertion sort.

```
for i = 1 to n
key = arr[i]
j = i - 1
// comparing whether the first element is greater than the second element
// if yes, then store the largest element to the next position
while j >= 0 and arr[j] > key
arr[j + 1] = arr[j]
j = j - 1
end while
// storing the smallest element in the correct position
arr[j + 1] = key
end for
```

We will now look into implementing insertion sort in C, C++, Java languages. In case you guys have solutions in other languages, then make sure you post it in the comments section of this article to help your friends.

C

C++

Java

Output

Input-
5
12 3 4 9 6
Output-
3 4 6 9 12

Similar to Bubble sort and Selection sort, the **time complexity of Insertion sort is also O(n). **This is because, in the worst case, i.e when the given array is in the exact reverse order as that of the output, each element has to be compared with all the n elements in the sorted array. So this makes it n*n.

- Best case time-complexity:
**O(n). This occurs when the given array is already sorted.** - Worst case time complexity:
**O(n)** - Space Complexity:
**O(1)**

Check out more Data Structure Questions

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×