Question

Write an algorithm to do insertion sort and analyse its run time complexity

Answer 1

When analyzing algorithms, the average case often has the same complexity as the worst case. So insertion sort, on average, takes O ( n 2 ) O(n^2) O(n2) time. Insertion sort has a fast best-case running time and is a good sorting algorithm to use if the input list is already mostly sorted.

The insertion sort algorithm iterates through an input array and removes one element per iteration, finds the place the element belongs in the array, and then places it there. This process grows a sorted list from left to right. The algorithm is as follows:

For each element A[i]A[i], if A[i]A[i] \gt > A[i+1]A[i+1], swap the elements until A[i]A[i] \leq ≤ A[i+1]A[i+1].

The animation below illustrates insertion sort: