# Insertion Sort

## Insertion Sort Algorithm

Insertion sort is a sorting algorithm in which an unsorted element is placed at the correct position in each iteration, that is, to the position to which it belongs in a sorted array.

Insertion sort is efficient as it reduces its total number of steps if a partially sorted array is provided as input.

Steps

• Store the second element of the array separately in `key.`
• Compare `key` with the first element.
• If `key` is less than the first element, insert it before the first element else insert it after the first element.
• Now, move to the third element and compare it with the elements to the left of it and then insert it in the correct position after comparison.
• Repeat the process until the entire array is sorted.

Visualisation of insertion sort with array = `{6, 2, 7, 3, 5, 4}` :

Code

``````void InsertionSort(int A[], int size)
{
for (int i = 1; i < size;i++)
{
int key = A[i];
int j = i - 1;
while (key < A[j] && j >= 0)
{
A[j + 1] = A[j];
--j;
}
A[j + 1] = key;
}
}
```

```

Each element is compared with all the other elements in the sorted array. For `N` elements , there will be `N^2` comparisons in the worst case. Therefore, the time complexity will be `O(N^2) in the worst case`

If the array is already sorted, then the time complexity will be ` O(n) `

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]