Insertion Sorting in Data Structure

Suppose an array P[] with n elements P[1], P[2],….,P[n] is in memory. The insertion sort algorithm scans P from P[1] to P[n], inserting each element P[k] into its proper position in the previously sorted sub-array P[1], P[2],…..,P[k-1].
Iteration 1: P[1] by itself is trivially sorted.
Iteration 2: P[2] is inserted either before or after P[1] so that P[1] and P[2] is sorted.

Algorithm for Insertion Sort:

Algorithm fnInsertionSort(P[],n)
{
for(Iteration=1;Iteration<n; Iteration++) { temp=P[Iteration]; for(j=Iteration-1; j>=0 && temp<P[j]; j--)
P[j+1]=P[j];
P[j+1]=temp;
}
} // End of Algorithm

Time complexity of Insertion Sort:

1. Best Case: If The array is in sorted order then only one comparison will be made in the inner loop. Therefore the total number of comparisons made will be decided by the outer loop which is n-1.
f(n)=(n-1)x1
T_b(n)=O(n)

2. Average Case: If we were given a random permutation, the chances of the kth insertion requiring 0, 1, 2,…,k-1 comparisons are equal and hence 1/k. The expected number of comparisons for the kth insertion is:
f(n)=1/2+2/2+……..+(n-1)/2
=n(n-1)/4
Therefore, T_a=O(n²)

3. Worst Case: The array is in reverse order. So for the first iteration 1 comparison is needed in the inner loop, for the second iteration 2 comparisons are needed and so on. Hence in the worst case:
f(n)=1+2+……….+(n-1)
=n(n-1)/2
T_w(n)=O(n²)

Space complexity of Insertion Sort:

The space complexity is O(1). Here also we don’t count the size of the array being sorted because that is given, not created specifically for this algorithm.