### What is insertion sort?

An algorithm that finds correct position for one element in each cycle. i.e, the position to which it belongs in sorted array.

### Time and Space Complexities:

- Best Time Complexity:
*O(n)* - Average Time Complexity:
*O(n^2)* - Worst Time Complexity:
*O(n^2)* - Best Space Complexity:
*O(1)*

### Steps to perform insertion sort:

- In first cycle, Get 2nd element and order it according to 1st element. i.e, if smaller place it before 1st element.
- In second cycle, get 3rd element and order it according to 1st and 2nd element. i.e, place them in ascending order.
- Now do the same in all subsequent cycles.
- Perform such (number of elements – 1) cycles.
- You will get sorted list.

### Pseudo code:

Initialize n = Length of Array InsertionSort(Array, n) { for i = 1 to n-1 { value = Array[i] position = i while (position > 0 and Array[position-1] > value) { Array[position] = Array[position - 1] position = position - 1 } Array[position] = value; } }