INSERTION SORT


Different steps involved in the insertion sort are as follows:

Step 1: The very First element a[1] of any array is already sorted . So from the start itself we have two subsections of our array as shown below .
A: a[1] | a [2] | …….| a [k] | a[k+1] | ……. | a [n-1] | a [n]
LEFT .........................../...................................... RIGHT
The left portion of the array is sorted while RIGHT one (Elements a[2] .. a[n] ) is unsorted.

Step 2: Choose any element (usually the first one) from the RIGHT / Unsorted
Array portion then INSERT that element into the sorted LEFT portion in its proper position after shifting the elements of the LEFT portion (if needed). In this way the LEFT / SORTED portion increases by one
element while the RIGHT /UNSORTED portion decreases by one.

Step 3: Repeat STEP 2 until the LEFT portion covers the entire array.


Let's take an example to show the insertion sort. We need to sort (27,19,33,15,4)

Iteration Num1Num2Num3Num4Num5
Iteration1 271933154
Iteration2 192733 154
Iteration2 1927 33154
Iteration3 19 2733154
Iteration4 151927334
Final Sorted 415192733

This is the iteration wise presentation for it.

The colored numbers represent the numbers that are under consideration in the respective iteration.They represent the numbers that are compared.

Pseudo code

INSERTION _SORT(A)
Start
1. For m= 2 to length [A] do
2. lock = A[m]
3. Arrange A[j] in sorted order
4. n ? m -1
5. while n > 0 and A[n] > lock do
6. A[n+1] = A[n]
7. n = n-1
8. A[i+1] = key

End

COMPLEXITY

CASE BEST CASE
AVERAGE CASE
WORST CASE
COMPLEXITY n-1 O(square of n)O(square of n)
ADVANTAGES:
1. Used most frequently by human beings in real life—ordering deck of cards
2. Efficient for small arrays.
3. Running time in best case is a function of n i.e linear as compared to SELECTION and BUBBLE sort which are quadratic in nature.
4. It uses no extra memory, it sorts in place.

Non-profit Tax ID # 203478467