INSERTION SORTDifferent steps involved in the insertion sort are as follows:
Step 1: The very First element a of any array is already sorted . So from the start itself we have two subsections of our array as shown below .
A: a | a  | …….| 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 .. 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)
This is the iteration wise presentation for it.
| Iteration1|| 27||19||33||15||4|
| Iteration2|| 19||27||33 ||15||4|
| Iteration2|| 19||27 ||33||15||4|
| Iteration3|| 19|| 27||33||15||4|
| Iteration4|| 15||19||27||33||4|
| Final Sorted|| 4||15||19||27||33|
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)
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
| CASE|| BEST CASE|| AVERAGE CASE|| WORST CASE|
| COMPLEXITY|| n-1|| O(square of n)||O(square of n) |
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.