Chapter 5.6, Problem 1QE

Program Plan Intro

Insertion sort

The algorithm is basically designed to organize and sort the array or list of elements in specific manner, that enables the system and user to get the final sorted array or a list of elements.

Generally, the insertion sort technique divides the list into two parts sorted or unsorted list. In the sorted list, the method assumes that one element of the list is already sorted and then it performs the operation on the unsorted list by inserting elements in its appropriate position in the sorted list.

The inversion of insertion sort in best case is $n-1$, in the worst case is $\frac{1}{2}\left(n^2-n\right)$ and in the average case is $\frac{1}{4}\left(n^2-n\right)$.