Implementing and Analyzing Insertion Sort

The insertion sort algorithm can be used to solve the sorting problem. In this article, we will look at how this algorithm is implemented, and how we can analyze its efficiency. To start, we will define the input and output of the algorithm.

Input: A sequence of n numbers, {a1,a2,…,an}

Output: A permutation, {b1,b2,…,bn} of the input, such that b1<=b2<=…<=bn

Insertion sort is efficient for sorting small numbers of elements but runs slower as the size of the set of numbers increases. The idea of the algorithm is to compare elements one at a time, swapping elements so that they are in the correct position. As an example, suppose we have the list of numbers shown below.

On the first pass of insertion sort, the algorithm compares the element 2 to the one previous, 5. It determines that 2 is less than 5, meaning they should switch places.

Once this is completed, it compares the next element 4 to 5. The element 4 is less than 5, so they must switch places.

After 4 and 5 switch places, we next need to compare 2 and 4 to determine if they also need to switch. In this case, 2 is less than 4, so no switch is required. The final comparison is comparing 6 to 5, which requires no switch, since 5 is less than 6. At this point, the algorithm is completed, and the list is sorted.

If we want to program this algorithm, we can use code like below: