9.2 Insertion Sort
Here in the ith iteration, the record a[i]
is inserted into its proper position in the first i positions.
Let us assume, for the sake of convenience, a fictitious record a
with key value = - .
for(i = 2;i <
= n;i + +)
j = i ;
while (key of a[j] < key of a[j
swap records a[j] and a[j
j = j - 1
Exhibits the worst case performance when the initial array is sorted in
Worst case and average case performance is O(n2)