Insertion sorting

Insertion Sorting


=============================================================
 

Use INSERTION SORT when you have a small number of elements to sort or the
elements in the initial collection are already “nearly sorted.”
Insertion Sort Complexity
Best O(n)
Average O(n^2)
Worst  O(n^2)

=================================================================
Insertion Sort Algorithm

Sort(Array)
for i=1to n-1 do
insert(Array,i,Array[i])
end

insert(Array,pos,value)
i=pos-1
while(i>=0 and Array[i]>value) do
Array[i+1]=Array[i]
--i
Array[i+1]=value
end
===========================================================================================

Cons
INSERTION SORT suffers from being too conservative for “random
data.
--
ANish