Sorting Problem: Insertion Sort

Learn to write programs with basic sorting strategies and see where we should apply them.

We'll cover the following

Insertion sort

Insertion sort is inspired by card sorting in a poker hand:

Click play to see the step-by-step methodology behind insertion sort, an algorithm we use to sort a deck of playing cards.

Inserting in a sorted array

Imagine there is already a sorted array up to the i-1 index. Think about the following:

How can we add the value at ith index inside the array such that following the addition, the array till ith index will be sorted?

Before addition:
1 3 4 7 2 ... (the first 4 values are sorted)
        ^
After addition
1 2 3 4 7 ... (5 values are sorted now)

We will compare the ith index with i-1 and swap if the value at the ith index is smaller. But that is not enough now because we still need to compare the value at the i-1 entry with i-2 value. We’ll see that similar swapping is needed, and we keep knocking to the left until we find the actual place where the value which was on the ith index is reached in the sorted order.

Step 1
1 3 4 7 2 ... (the first 4 values are sorted)
        ^
Step 2
1 3 4 2 7 ... (2 is shifted once)
      ^
Step 3
1 3 2 4 7 ... (2 is shifted twice)
    ^
Step 4
1 2 3 4 7 ... (2 is shifted thrice)
  ^
Stop (it is sorted)

If you look below carefully, you’ll see we require two stopping criteria—i-1>=0 and A[i-1]>A[i]—because we don’t want to go beyond the array indexes to the left and the left value should be smaller than the right.

Press + to interact
// Insertion of ith element in the sorted array of A[0...(i-1)]
while(i-1>=0         // the left neighbor shouldnt cross the 0 boundary
       && A[i-1]>A[i])
{
    swap(A[i-1], A[i]);
    i--;
}

Implementation of insertion sort

We can build on this idea of insertion by first assuming that we have an array of size = 1 only (and A[0] is already sorted) and i = 1 is to be inserted inside the sorted array to the left A[0...0].

Press + to interact
void insertionSort(int A[ ], int size)
{
    for(int va=1; va<size; va++)
    {
        int i=va;  // va is the value at index to be added and we assume that 
                // before every while's beginning A[0...(va-1)] is already sorted.
        while(i-1>=0 && A[i-1]>A[i])
        {
            swap(A[i-1], A[i]);
            i--;
        }
    }
}

Insertion sort

Question 1

What if we change the order of conditions, i.e., while(A[i-1]>A[i] && i-1>=0) or while(A[i-1]>A[i] && i>0)?

Show Answer
Question 2

If the array is already sorted, how many times will the inner while loop execute?

Show Answer
Question 3

What is the worst input in this insertion sort? How many swaps will happen in such a scenario?

Show Answer
Question 4

What is the best scenario? In other words, in which scenario will there be the minimum number of swaps? And how many?

Show Answer

Insertion sort function

Just like the selection of selection sort and bubble-up of bubble sort, we may have the following function:

void insertion_in_sorted(int A[], int i);

This function will assume that the array A[0... i-1] is sorted while the A[i]th element may not be sorted. We want that the ith element is repositioned in the array A[0...i].

Let’s write down a complete code of insertion sort below with functions:

7 3 6 5 8 2 1 9
Insertion sort solution