# Insertion Sort Algorithm

Insertion sort is a simple and efficient sorting algorithm that works the way we sort playing cards in our hands. It is based on the idea that one element from the input elements is consumed in each iteration to find its correct position i.e, the position to which it belongs in a sorted array.

**Algorithm**

In Insertion sort we assume two subarray one is sorted and another is unsorted. Initially the size of the sorted array is zero. Now, in each iteration insertion sort maintain the following two property:

*Size of the sorted subarray is increase by one in each iteration.**Sorted array is always sorted.*

To accomplish the above property, in each iteration:

- We pick one element from the unsorted array.
- Find the proper location in sorted array and place the element in sorted array.

This last step of the algorithm is accomplished either by linear search or binary search.

**Following figure illustrate insertion sort for the array \(<7, 4, 5, 2>\).**

**Implementation of Insertion Sort**

#include<stdio.h> void printArray(int arr[], int size){ for(int i = 0; i < size; i++){ printf("%d ", arr[i]); } printf("\n"); } void insertionSort(int arr[], int size){ int i, j, key; for(i = 1; i < size; i++){ key = arr[i]; j = i-1; //find proper position for key using backward //linear search in arr[i-1...0] while(j >= 0 && arr[j] > key){ arr[j+1] = arr[j]; j = j - 1; } arr[j+1] = key; } } // Driver Program int main(){ int arr[] = {5,3,1,9,8,2,4,7}; int size = sizeof(arr)/sizeof(arr[0]); insertionSort(arr, size); printf("======Sorted Array is======\n"); printArray(arr, size); return 0; }

**Performance**

**Time Complexity:** Insertion sort take \(n\) iteration to move all the element in to the sorted subarray. In each iteration it linearly search to find the proper location of the element. So in \(i^{th}\) iteration in worst case we need \(i\) moves. So total time required is:

$$T(n) = 1 + 2 + 3 + … + (n-1) = \frac{n(n-1)}{2}$$

Hence, we get \(\bbox[pink, 5px]{T(n) = \mathcal O(n^2)}\)

**Can we improve this time complexity?**

We can use binary search to reduce the number of comparisons in normal insertion sort. In Binary Insertion Sort we use binary search to find the proper location to insert the selected item at each iteration. In normal insertion, sort it takes \(\mathcal O(i)\) (at\(i^{th}\) iteration) in worst case. we can reduce it to \(\mathcal O(\log i)\) by using binary search. The algorithm as a whole still has a running worst case running time of \(\mathcal O(n^2)\) because of the series of moves required for each insertion.

**Space Complexity: \(\mathcal O(1)\)**

**Algorithmic Paradigm:** Incremental Approach

**Sorting In Place:** Yes

**Stable:** Yes

**Online:** Yes

**Uses:** Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.