Insertion Sort
Sorting : - Input: A Sequence of n numbers (a 1 ,a 2 …….a n ). Output : A permutation (recording) <a’ 1 ,a’ 2 ,….a’ n > of the input sequence such that a’ 1 <=a’ 2 <=,….<=a’ n . Insertion Sort Insertion sort is an efficient sorting algorithm for sorting a small number of elements. Insertion sort works the way people sort a hand of playing card. We start with empty hand and card face down on the table. We remove one card at a time from the table and insert it into the correct position in the left hand. For correct position of card we compare it with each of the card already in the hand in left. algorthms-cormen Algorithm INSERT-SORT(A) for j <-- 2 to length[A] do key <-- A[j] Insert A[j] into the sorted sequence A[1.... j-1] i <-- 1 while i > 0 and A[j] > key do A[i+1] <-- A[i] i <-- i-1 A[i+1] <-- key Ex: A = (5,2,4,6,1,3) the index j indicate the