Insertion Sort

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:

1. In first cycle, Get 2nd element and order it according to 1st element. i.e, if smaller place it before 1st element.
2. In second cycle, get 3rd element and order it according to 1st and 2nd element. i.e, place them in ascending order.
3. Now do the same in all subsequent cycles.
4. Perform such (number of elements – 1) cycles.
5. 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;
    }
}

Let’s Code

To code in any language other than C++, 👉 Click here 👈