Insertion Sort

If the             
  

               first few objects are already sorted, an unsorted object can be inserted in the 

sorted set in 

 proper place. This is called insertion sort. 

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.

Algorithm:

It works the way you might sort a hand of playing cards:

1. We start with an empty left hand [sorted array] and the cards face down on the 

table.

2. Then remove one card [key] at a time from the table [unsorted array], and insert it into the correct position in the left hand [sorted array].

3. To find the correct position for the card, we compare it with each of the cards already in the hand, from right to left.

^^ ...  Note that at all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table.

Pseudocode:

        We use a procedure INSERTION_SORT. It takes as parameters an array A[1.. n] and the length n of the array. The array A is sorted in place: the numbers are rearranged within the array, with at most a constant number outside the array at any time.

INSERTION_SORT (A)

1.     FOR j ← 2 TO length[A]

2.             DO  key ← A[j]   

3.                   {Put A[j] into the sorted sequence A[1 . . j − 1]}  

4.                    i ← j − 1   

5.                    WHILE i > 0 and A[i] > key

6.                                 DO A[i +1] ← A[i]            

7.                                         i ← i − 1    

8.                     A[i + 1] ← key

Example: Following figure (from CLRS) shows the operation of INSERTION-SORT on the array A= (5, 2, 4, 6, 1, 3). Each part shows what happens for a particular iteration with the value of j indicated. j indexes the "current card" being inserted into the hand.

Best-Case:

The best case occurs if the array is already sorted. For each j = 2, 3, ..., n, we find that A[i] less than or equal to the key when i has its initial value of (j − 1). In other words, when i = j −1, always find the key A[i] upon the first time the WHILE loop is run.

T(n) = an + b = O(n)

It is a linear function of n.

Worst-Case:

The worst-case occurs if the array is sorted in reverse order i.e., in decreasing order. In the reverse order, we always find that A[i] is greater than the key in the while-loop test. So, we must compare each element A[j] with each element in the entire sorted subarray A[1 .. j − 1] and so tj = j for j = 2, 3, ..., n.

T(n) = an2 + bn + c = O(n2)