Insertion Sort

Guys,We all have studied the bubble and selection sorting in our school.This is another type of sorting..

Insertion sort is a n effective algorithm for small set of data.The idea comes from this......When we play a game of cards we usually sort it.We place all the cards face down on the table and start with an empty left hand.Then we pick up one card from the table and place it in our left hand at its correct position.Like this we go on picking up cards from table and placing them in the correct positions in the left hand until all cards are picked up.Every time we pick up a card the ones in our hand are already sorted.
Hence the pseudocode for this algorithm goes like this.....

Insertion-sort(a) //where a is the array
for j=2 to a.length //because the first card is already sorted
key=a[j]
//insert a[j] in the sorted sequence a[1...j-1]
i=j-1
while i>0 and a[i]>key
a[i+1]=a[i]
i=i-1
a[i+1]=key

The worst case time complexity is O(n^2)