##### Best example of insertion sort is sorting deck of cards. .. As you see in the figure, say we have 2,4,5 10 and 7 clubs in our hand and we have to sort it .

##### As we know, we will take 7 clubs and place it between 5 and 10 clubs. Hence, for each card we need to swap the cards before it and place the key card in place .

##### Before the analysis , lets have a look at pseudo code of insertion sort. For input array A

INSERTION-SORT(A) for j <-- 2 to length [A] do key <-- A[j] i <-- j - 1 while i > 0 and A[i] > key do A[i + i] <-- A[i] i <-- i - 1 A[i + 1] <-- key

##### I tried implementing the same in C++. Here is the code

#include <iostream> using namespace std; int main() { int arr[] = {5,2,4,6,1,3}; int arrSize = sizeof(arr)/sizeof(arr[0]); int key; int i; for(int j=1; j<arrSize; j++) { key = arr[j]; i = j - 1; while(i >= 0 && arr[i] > key) { arr[i+1] = arr[i]; i = i - 1; } arr[i+1] = key; } for(int i=0; i<arrSize; i++) cout << arr[i] << " " << endl; return 0; }

Output is :

##### Before we start our analysis of the insertion sort, we will see how many times each statement runs.

INSERTION-SORT(A) for j <-- 2 to length [A] ---------------------------- runs n times do key <-- A[j] -------------------------------------- runs n-1 times i <-- j - 1 -------------------------------------- runs n-1 times n while i > 0 and A[i] > key --------------------------- ∑ tj j=2 n do A[i + i] <-- A[i] -------------------------------- ∑ tj - 1 j=2 n i <-- i - 1 ------------------------------------------ ∑ tj - 1 j=2 A[i + 1] <-- key ------------------------------------- n-1

##### Now, lets get into the analysis part.

##### Okay, In each statement , we do some operations as well i.e – increment, decrement, counter — all those are considered to be constants. Hence we name constants from c1 to c7

##### And also, tj is the function which does while loop operation .

##### If the input is already sorted, there would be no in-swapping takes place. i.e. While loop will never be executed. Since while loop is inside FOR loop which runs from 2 to n , we enclose it with sigma j = 2 to n.

##### Hence the equation would be

##### What could be the Best case ?? — A sorted input

##### and what could be the worst case input . — Input sequence in reverse order.

#### These 3 screenshots will explain how insertion sort is O(n) in best case and O(n square) in worst case.

##### This you tube video will be helpful to understand the same

https://www.youtube.com/watch?v=yXwFrc5GS6A — click the view the video