Insertion sort

As kids, we all used to love card games. Some of us still do. Do you remember, though, how you arranged and sorted the cards in your hand while playing such games? If you are somewhat like me, once you had all the cards in your hands, you would start from the left side and pick them one by one, from left to right. If the selected card is lower than the previous one, you push the previous card to the right to make space for the new card. You continue doing so until the current card is greater or equal to the one on the left. Finally, you insert the selected card in that position.

This is exactly the idea behind insertion sort, a widely used algorithm when it comes to solving the famous sorting problem, which you are already familiar with. In this topic, we will cover in detail the algorithm itself, as well as its advantages and disadvantages, so that you know precisely when to use it and when to look for alternatives instead. So, let's get started!

Algorithm description

Roughly speaking, insertion sort is a simple sorting algorithm that sorts one element at a time. It automatically divides the array into the sorted and the unsorted part, as we will explain below. At each iteration, the algorithm moves an element from the unsorted part to the appropriate position in the sorted one, until it sorts all array elements.

Formally, the algorithm works as follows:

1. Assume the leftmost element belongs to the sorted part of the array, and all remaining elements are in the unsorted part;

2. Choose the first element from the unsorted part and insert that element into the sorted list at its proper position;

3. Repeat step 2, until all elements are sorted.

How to perform insertion at step 2? Compare the selected element with its left neighbor: if it is greater than or equal to it, the element is already in its proper position. Otherwise, move the neighbor one position to the right to make space for the current element. Now, it has a new left neighbor: repeat the same procedure until our element reaches the desired position, i.e. is greater than or equal to the element on its left, and finally, insert it there.

Example

Let's forget for a while about the happy times when we used to play cards and not worry about everything else, and remember the exam papers, grades, and all the stuff of that sort. Suppose you are a teaching assistant of Dr. Poulad, a Computer Science professor. Her students have just had an exam, and she has already graded their papers. Now, Dr. Poulad has asked you to arrange them in ascending order, i.e., from the lowest to the highest score.

The array has six elements, the first element's index is 0, and the last element has the index 5. The following image illustrates how the insertion sort algorithm works:

Let's explain in detail the first few steps:

1. The sorted part includes only a single element with the index 0, since it's the leftmost element in the array. Let's look at the second one ($23$). It's greater than the last element in the sorted part, which means we don't move it.

2. Now, the sorted part includes elements with the indexes 0-1. We consider the element with the index 2 ($19$). It's smaller than the last element in the sorted part, hence, we move the last element, namely $23$, to the right. Still, the new neighbor, $21$, is greater than our element, therefore, we push $21$ to the right and insert $19$ in this position. Now, after moving, it has index 0.

Similarly, we keep applying the steps of the algorithm to the rest of the elements, as shown in the illustration above. At step 6, the unsorted part is empty, which means the whole array is sorted. Now you can be proud of yourself, since you've completed the professor's task!

Seeing a visualization of the insertion sort algorithm might help you get the gist of it. You can skip the lecture mode by clicking X on the top right corner and select INS.

Pseudocode

i = 1                            // we skip index 0, as it is within the sorted part
while i < length(A):             // we will check all the elements in the unsorted part
    x = A[i]                     // save the value of the selected element
    j = i - 1                    // take the index of the left neighbor
    while j >= 0 and A[j] > x:   // comparing our selected element with its left neighbors
        A[j+1] = A[j]            // if our element is lower, push the neighbor to the right
        j = j - 1                // move left to the next neighbor
    A[j+1] = x                   // the proper position has been reached, insert our element there
    i = i + 1                    // examine the next element in the unsorted part

// N.B. We could simply swap x and A[j] in line 6, but this would take more time, 
// since we would need to perform extra assignments during each iteration.
// Instead, we perform only one assignment in line 6.

Complexity and other features

Every algorithm has its advantages and shortcomings, and insertion sort is not an exception. Our algorithm works pretty fast with already sorted arrays. It takes $O(n)$ time, because the elements are already in their proper positions, so we don't need to move anything. In pseudocode language, this means that the inner while cycle will not be executed. Another great advantage of the insertion sort algorithm is its simple implementation and the human-like logic behind it. Also, it is worth mentioning that our algorithm is stable and in-place, meaning that it doesn't require any extra memory.

With the insertion sort's features we've mentioned, we can conclude that it is advisable to use this algorithm for arrays that contain few elements or are almost fully sorted. Such examples are sets of data produced by another program, sorted datasets, in which we need to append a few new elements, error log files, etc.

However, quite the opposite happens with the algorithm's efficiency in the average and worst cases. When this happens, insertion sort's time complexity is quadratic, since both while loops will be executed. For example, if the array is in reverse order, we need to compare every pair of elements and make $\frac{n(n-1)}{2}$ comparisons, which is $O(n^2)$.

Conclusion

In this topic, we've introduced a new sorting algorithm, namely insertion sort. Here's a summary of what we've learned:

• We can implement the algorithm easily by following these steps: divide the array into the sorted and the unsorted part. During each iteration, take the first element from the unsorted part and insert it into the sorted list at its proper position. Iterate this step until all the elements are sorted.

• Insertion sort's best-case complexity is $O(n)$, while in the average and the worst-case scenario, the algorithm takes $O(n^2)$ time to complete its work.

• It's best to use this algorithm for arrays with few elements or almost-sorted datasets.

• Avoid using insertion sort for large sets of data.

Now you are perfectly equipped with knowledge and are ready to proceed with the tasks.