# Insertion Sort

- Insertion Sort Algorithm
- Insertion Sort Example
- Insertion Sort Algorithm Implementation
- Insertion Sort Algorithm Complexity

Insertion sort is a simple comparison-based sorting algorithm. In this algorithm, we maintain two subarrays: a sorted and an unsorted subarray. One element from the unsorted subarray finds its correct position in the sorted subarray and gets inserted there. It is analogous to the way when someone sorts a deck of cards in their hand. It is named insertion sort because it works on inserting an element at its correct position. This algorithm is efficient for small datasets but not suitable for large datasets.

## Insertion Sort Algorithm

Let us assume that we have an unsorted array `A[]`

containing n elements. The first element, `A[0]`

, is already sorted and in the sorted subarray.

##### We mark the first element from the unsorted subarray

`A[1]`

as the key.##### The key is then compared with elements from the sorted subarray; here, we have only one element,

`A[0]`

.##### If the key is greater than

`A[0]`

, we insert it after`A[0]`

.##### Else if it is smaller, we compare again to insert it at the correct position before

`A[0]`

. (In case of`A[0]`

, there is only one position)##### Take the next element

`A[2]`

as key. Compare it with sorted subarray elements and insert after the element just smaller than`A[2]`

. If there are no small elements, then insert it at the beginning of the sorted subarray.##### Repeat the above steps for all the elements in the unsorted subarray.

## Insertion Sort Example

Suppose we have the array: `(5,3,4,2,1)`

. We will sort it using the insertion sort algorithm.

Sorted subarray | Unsorted Subarray | Array |
---|---|---|

( 5 ) | ( 3, 4, 2, 1) | (5, 3, 4, 2, 1) |

- First Iteration

Key : `A[1]`

= 3

Sorted subarray | Unsorted Subarray | Array |
---|---|---|

( 3 , 5) | (4, 2, 1) | (3, 5, 4, 2, 1) |

- Second Iteration

Key : `A[2]`

= 4

Sorted subarray | Unsorted Subarray | Array |
---|---|---|

( 3, 4, 5) | (2, 1) | (3, 4, 5, 2, 1) |

- Third Iteration

Key : `A[3]`

= 2

Sorted subarray | Unsorted Subarray | Array |
---|---|---|

( 2, 3, 4, 5) | (1) | (2, 3, 4, 5, 1) |

- Fourth Iteration

Key : `A[4]`

= 1

Sorted subarray | Unsorted Subarray | Array |
---|---|---|

( 1, 2, 3, 4, 5) | () | (1, 2, 3, 4, 5) |

## Insertion Sort Algorithm Implementation

```
#include<iostream>
using namespace std;
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++)
{
int j = i;
while (j > 0 && arr[j - 1] > arr[j])
{
int key = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = key;
j--;
}
}
}
int main() {
int n = 5;
int arr[5] = {5, 3, 4, 2, 1};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
insertion_sort(arr, n); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
```

## Insertion Sort Algorithm Complexity

### Time Complexity

- Average Case

On average, `i`

comparisons are made in the `ith`

pass of insertion sort. So if there are n iterations, then the average time complexity can be given below.

```
1 + 2 + 3 + ... + (n-1) = n*(n-1)/2
```

Hence the time complexity is of the order of [Big Theta]: O(n^{2}).

- Worst Case

The worst-case occurs when the array is reversely sorted, and the maximum number of comparisons and swapping has to be performed.

The worst-case time complexity is [Big O]: O(n^{2}).

- Best Case

The best-case occurs when the array is already sorted, and then only the outer loop is executed n times.

The best-case time complexity is [Big Omega]: `O(n)`

.

### Space Complexity

Space Complexity for the insertion sort algorithm is `O(n)`

because no extra memory other than a temporary variable is required.