# 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 `i`

th index with `i-1`

and swap if the value at the `i`

th 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 `i`

th 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.

// 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]`

.

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

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)`

?

If the array is already sorted, how many times will the inner `while`

loop execute?

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

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

### 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 `i`

th 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