### Insertion Sort Algorithm - Java Applet Visualization

 The gadget spec URL could not be found Insertion Sort :  This basically inserts each element of the into its proper position . The first two elements are put in sorted order ; after that the first three elements are put in order .. and this goes on progressively . eg. 8,2,4,3,1 First focus on just 8,2 ( first 2 elements )  ;  2 needs to be placed before 8  => 2,8,4,3,1  Now focus on 2,8,4 ( first 3 elements )  4 needs to be placed between 2 and 8  => 2,4,8 ,3,1 Focus on 2,4,8,3 ( first 4 elements ) Move 3 between 2 and 4  => 2,3,4,8 ... and so on . This is an example of dynamic programming . The parts of the problem of smaller size are solved first . And we keep incrementing on this solution . When you are considering the first X elements  We already know that the first X-1 elements are sorted .  So you only need to bring down the X-th element into its correct position , and all the elements after will have their indexes incremented by 1 .  for i -> 0 to lastIndex - 1     key = array[i]     j = i-1      while(j >=0 && array[j]>key )          array[j+1] <- array[j]     array[j]<- key  next i "Start" the visualization below .