Insertion Sort Algorithm and its

correctness
 Sorting Problem

Input : A sequence of n numbers <a1,a2,a3,a4,...,an>

Output: A permutation (reordering) <a1',a2',a3',a4',...,an'>
of the input sequence such that
a1'<= a2'<=a3' <=a4'<=.....<=an'
● An algorithm for sorting : Insertion sort
●Works in the same way as many people sort a hand of
playing cards
● Start with an empty left hand and all cards face down
on the table
● Remove one card at a time from the table and insert
it to the correct position in the left hand
 Observations
● When we take any card (say key card), we
start comparing it with the last card in our
left hand.
● If the value of the key card is less than the
last card in our left hand, then only we
proceed with further comparisons
● If the value of the key card is equal to or
greater than the last card in our left hand,
then we place the key card as the last card.
● This action is performed based on an
observation that cards in the left hand is
already sorted
● At any time, we are inserting to a sorted list
of elements.
Working of Insertion Sort algorithm
● What is the input of our algorithm?
● Input: array of elements 5, 7, 2, 3, 7, 10 .
● Pass the input array to the function insertion sort
5 7 2 3 7 10

● Keep 5 as such in the first position of the array,

assuming that it is sorted by itself
5 7 2 3 7 10

● Take 7, key=7, compare it with 5, place it there itself

5 7 2 3 7 10
 5 7 2 3 7 10

● Take 2, we put in a temporary variable (say

key), we shift 7 to 2's position in the array,
key=2
●
Now the array looks like,
5 7 7 3 7 10

● Now, compare key(2) with 5, we shift 5 to next

position in the array
● Now the array looks like,
5 5 7 3 7 10

• Then, place the key value in the first position

2 5 7 3 7 10
 2 5 7 3 7 10

● Now key=3

2 5 7 7 7 10

2 5 5 7 7 10

2 3 5 7 7 10
 2 3 5 7 7 10

● Now key=7

2 3 5 7 7 10

● Now key=10

2 3 5 7 7 10
Few tips on the Design of algorithm:

● How many loops we should have?

● One loop for sure which goes from 1 to n
● Another loop which goes from position of key
element to 1 ?
Insertion Sort Algorithm:

INSERTION SORT(A)
1. for j=2 to [Link]
2. key = A[ j ];
3. //Insert A[ j ] into the sorted sequence A[1...j-1]
4. i = j-1
5. while i > 0 and A[ i ] > key
6. A[ i+1 ]=A[ i ]
7. i=i-1
8. A[ i+1 ]= key
 Trace INSERTION SORT(A) INSERTION SORT(A)
1. for j=2 to [Link]
2. key = A[ j ];
3. //Insert A[ j ] into the sorted
sequence A[1...j-1]
4. i = j-1
● Input : 5, 2, 4, 6, 1, 3 5. while i > 0 and A[ i ] > key
● First iteration of for loop , with j=2 6. A[ i+1 ]=A[ i ]
● Key = 2, i=1 7. i=i-1
● while loop is executed as i>0 and A[i]>key 8. A[ i+1 ]= key

● A[2] = 5, i=0
● while loop fails to execute as i=0
● A[ 0+1] =2
● Intermediate output after the 1st iteration of for loop : 2, 5, 4, 6, 1, 3
Operations of insertion sort on an array
A = 1, 4, -2, -3
● After 1st iteration of while loop, with j = 2, i = 1: A = 1, 4, -2, -3
● After 1st iteration of for loop, with j = 2 : A = 1, 4, -2, -3

● After 1st iteration of while loop, with j = 3, i = 2: A = 1, 4, 4,-3

● After 2nd iteration of while loop, with j = 3, i = 1: A = 1, 1, 4,-3
● After 2nd iteration of for loop, with j = 3 : A = -2, 1, 4, -3

● After 1st iteration of while loop, with j = 4, i = 3: A = -2, 1, 4, 4

● After 2nd iteration of while loop, with j = 4, i = 2: A = -2, 1, 1, 4
● After 3rd iteration of while loop, with j = 4, i = 1: A = -2, -2, 1, 4
● After 3rd iteration of for loop, with j = 4 : A = -3, -2, 1, 4
Design Paradigm: Incremental Approach

An algorithm consider the elements one at a time,

inserting each in its suitable place among those
already considered (keeping them sorted).

Insertion sort is an example of an incremental

algorithm; it builds the sorted sequence one number
at a time.

Simplest example of the incremental insertion

technique
build up a complicated structure on n items by first
building it on n − 1 items and then making the
necessary changes to fix things in adding the last
item.
In place sorting Algorithm

● Insertion sort is an in place sorting

method ie it rearranges the numbers
within the input array, with at most a
constant number of them stored outside
the array at any time.

● The input array A contains the sorted

sequence after the procedure is finished
How do we prove that INSERTION SORT(A) is correct?

● We observe the algorithm critically and try to understand

● We observe that :
● The index j indicates:
● The current number/card being inserted
● At the beginning of each iteration of for loop indexed by j:
A [1 .. j-1 ] is sorted and A [ j+1..n ] is remaining
● Elements A [ 1.. j-1 ] are the elements originally in
positions 1 through j-1, but now in sorted order
● We state these properties of A[ 1 .. j-1 ] formally as a loop
invariant
 Loop Invariant of INSERTION SORT(A)

● At the start of each iteration of the for loop of lines 1-8,

the subarray A [1 ... j-1] consists of the elements originally
in A [ 1 ... j-1], but in sorted order.
● We use loop invariant (a property of the algorithm) to prove
that the algorithm is correct
● We must show three things about a loop invariant:
● Initialization
● Maintenance
● Termination
 Correctness of Insertion Sort

● We must show three things about a loop invariant :

● Initialization: The loop invariant is true prior to the first
iteration of the loop
● Maintenance: If the loop invariant is true before an
iteration of the loop, it remains true before the next
iteration
● Termination: When the loop terminates, the loop invariant
gives us a useful property that helps us to show that the
algorithm is correct
● When the first two properties hold, the loop invariant is true
prior to every iteration of the loop.
 Loop Invariant vs Mathematical
Induction
● Invariant holds before the first iteration ~ base case of
mathematical induction
● Invariant holds from iteration to iteration ~ inductive step
● Third property ie. The termination property differs from
Mathematical induction
● In Mathematical induction, we use the inductive step
infinitely, whereas here we stop the induction when
the loop terminates
 Proof – Correctness of Insertion sort

● Initialization: Loop invariant trivially holds before the first

loop iteration. A [1] is sorted by itself.
● Maintenance:
● for loop works by moving A[ j-1 ], A[ j-2 ], A[ j-3 ] and
so on by one position to the right and finds the proper
position for A[ j ] and inserts the value of A[ j ].
● Hence, A[ 1..j-1 ] consists of the elements originally in
A [ 1..j-1 ], but in sorted order.
● Incrementing j for the next iteration preserves the
loop invariant
 Proof: Correctness of Insertion sort -contd.

● Termination:
● for loop terminates when j > [Link] = n ie.
j = n+1
● Substituting n+1 in the wording of loop
invariant, the subarray A[ 1..n ] consists of
originally in A[ 1..n ], but in sorted order
● Observe that A[ 1..n ] is the entire array and
since the entire array is sorted, the algorithm is
correct.