Understanding Insertion Sort for coding interviews

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

Unsorted array to be sorted with Insertion sort

Here is the strategy:

  1. 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)
  2. 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.
  3. Now the sorted list ( sorted area of the array has 2 elements)
  4. Now again pick the element next to the sorted area , i.e., element 3 and repeat step # 2
  5. 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 1

Insertion Sort 2

Insertion Sort 2

Insertion Sort 3

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);



Analysis of Insertion Sort

Sort PropertyAnalysis
Time ComplexityThe 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 ComplexitySince the array is sorted in place and no extra space is used, the space complexity is O(1)
AdaptableIf 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
StableInsertion 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 SwapsInsertion 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

When to use and when to avoid Insertion Sort ?

Use insertion sort in the following scenarios:

  1. When the array is nearly sorted – since insertion sort is adaptive
  2. When we have memory usage constraints
  3. When a simple sorting implementation is desired
  4. When the array to be sorted is relatively small
  5. When you need to sort elements online – that is sorting them as they come in.

Avoid using insertion sort when:

  1. The array to be sorted has a large number of elements
  2. The array is completely  unsorted
  3. You want a faster run time and memory is not a concern.