An efficient algorithm for sorting a small number of elements.Though it has a worst cae running time of O(n^2),it is in general much faster in two cases :

(i) The small constant factors in insertion sort make it faster for small n.

(ii) It is faster when parts of input list are already sorted. After k passes(where each pass requires at the most scanning all elements of the list)the first k elements of the list are sorted.Since each pass has a worst case running time of O(n) and there are total of n passes,therefore the worst case running time of insertion sort is O(n*n)



Applet page