Understanding Insertion Sort for coding interviews

September 21, 2019 Deb Haldar

In the last post we looked at how to really understand Bubble Sort by solving it on paper, one step at a time. We’ll take the same approach for Insertion Sort.

As with most fundamental sorting algorithms, the chances of this showing up in a FAANG interview is minimal. The one curious case when you should implement this algorithm is when you’re asked to sort a collection Online, that is as you receive each element.

Strategy for Insertion Sort

Given an unsorted array of integers, we want to sort them in ascending order. The array under consideration is shown below:

Unsorted array to be sorted with Insertion sort

Here is the strategy:

Start with a sorted sub-list of size 1 ( a list of size 1 is by definition sorted since there is only one element in it)
Take the element adjacent to the sorted area. Insert this element into the right place in the sorted area. This is accomplished by bubbling down the element to the correct spot in the sorted area.
Now the sorted list ( sorted area of the array has 2 elements)
Now again pick the element next to the sorted area , i.e., element 3 and repeat step # 2
Repeat the process untill the entire array is sorted.

Visualize the algorithm on paper

Again, this is the most important part to understand in this article. It’s not the code or the analysis, but solving it on paper. If you can do this, everything else will be a piece of cake.

Insertion Sort 1

Insertion Sort 2

Insertion Sort 3

At this point, the sorted area has grown to encompass the entire array. We’re all done !

Note: I’d highly recommend that you try this on paper – this’ll help you really understand the insertion sort algorithm and remember it in the long term. Also, this is good practice for explaining the algorithm to your interviewer on a whiteboard.

Implementing Insertion Sort in C#

using System;

namespace Sorting
{
    class InsertionSort
    {
        public static bool debug = false;
        public static void Sort(int[] inputArr)
        {
           for(int i=0; i< inputArr.Length -1; i++)
            {
                //Bubble down the samller element to it's correct position in the sorted part of 
                // the array
                for(int j=i+1; j > 0; j--)
                {
                    if(inputArr[j] < inputArr[j-1])
                    {
                        Utilities.Swap(inputArr, j, j - 1);
                    }
                    else
                    {
                        break;
                    }

                    if(debug)
                    {
                        Utilities.PrintArray(inputArr);
                    }
                }
            }
        }

    }
}

Analysis of Insertion Sort

Sort Property	Analysis
Time Complexity	The worst case is when the entire array is sorted in descending order. In that case, we have to check N elements and swap N elements for each selected element. Hence the time complexity is O(N^2)
Space Complexity	Since the array is sorted in place and no extra space is used, the space complexity is O(1)
Adaptable	If the array is partially sorted, we’ll terminate the sorting loop early. In other words, nearly sorted arrays complete very quickly. Hence insertion sort is adaptive
Stable	Insertion sort is a stable sorting algorithm. As elements bubble to the correct position in the sorted area of the array, the original relative order of equal elements are maintained.
Number of Comparisons and Swaps	Insertion Sort makes O(N^2) comparisons ( every element is compared to every other element).Insertion Sort makes O(N^2) swaps to get all elements in the correct place