What Is Insertion Sort, and How Does It Work? (With Examples)

When it comes to sorting an array of data, there are many sorting algorithms you can use. One of the easiest algorithms to use is insertion sort, due to its relative simplicity and intuitive nature. Read on to explore exactly what insertion sort is, how it’s implemented, and what it can be used for, with an example.

What Is Insertion Sort?

Insertion sort is a sorting algorithm, one of the methods you can use to sort an array. The way that it works isn’t too complicated to understand and can be largely compared to how you would sort a deck of cards.

In this case, we would start off by assuming the first card in the deck is already sorted. Then, we select an unsorted card and sort it. This is done by comparing it to the first card. If the selected card is greater than the sorted card, it’s placed in a position to the right of the first card. If the card in question is less than the sorted card, it’s placed in a position to the left.

This process continues until all of the unsorted cards are placed in their correct positions. Insertion sort functions in a very similar way. Each unsorted data value is sorted through the same kind of iterative process.

Since insertion sort is a quite simple algorithm, it’s best used for relatively small data sets, as well as those that are already somewhat sorted. In this way, it’s known as an adaptive and efficient algorithm. Next, we’ll run through the theory behind how insertion sort works.

The Algorithm Behind the Insertion Sort

The insertion sort method can be concisely represented with the following pseudocode:

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort

In simple terms, this means that the first element is assumed to be sorted. Each subsequent element is compared to the first element. If it’s smaller than the sorted element, it’s moved down to the first, or 0^th position. If it’s greater, it’s moved one position to the right. Iterations continue until all elements have been sorted.

The Inner Workings of Insertion Sort

Now we’ve covered how insertion sort works and the theory behind it, it’s time to illustrate the process with a suitable array. If we consider the following data set:

We can assume the first element, 10, is already sorted. After this, we take the second element, 14, and store it separately. Comparing 14 to 10, we can see that it’s greater, so it retains its position as the second element. This is the first iteration, known as the first pass. The first element, 10, is stored in a subarray.

Where green = sorted array

For the second pass, we move on to the third element, which is 5. This is compared to the previous elements. We can tell it’s smaller than the previous element, 14, so it swaps places with 14.

The algorithm then compares it to the elements in the sorted subarray. 5 is also smaller than 10, so it’s moved to the beginning of the subarray. The sorted array now has 2 elements — 5 and 10.

Now, we move on to the third pass. In this case, 7 is the selected element. This is smaller than 14, so it’s moved one position to the left and into the sorted array. This isn’t the correct position, though, as 7 is smaller than 10 but greater than 5. Therefore, it’s moved another position to the left.

For the fourth pass, we’re looking at the fourth element, which is 14. This is already sorted, so now the sorted array includes 5, 7, 10, and 14.

The Final Result

Lastly, for the fifth pass, we take the fifth element, which is 1. This is clearly smaller than 14, so the position is swapped. It’s also smaller than 10, so the position is swapped again. This continues two more times, as 1 is the smallest element in the array. Therefore, we end up with a sorted array as follows:

The Implementation of Insertion Sort

Insertion sort can be implemented with a variety of programming languages, from C, C#, and C++ to Java, Python, PHP, and Javascript. For illustrative purposes, we’re going to be working with Python. The whole process can be represented in the following code:

def insertionSort(arr):
if (n := len(arr)) <= 1:
return
for i in range(1, n):
key = arr[i]
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
arr = [10, 14, 5, 7, 1]
insertionSort(arr)
print(arr)

First, we’re defining the insertion sort as a function of the array, (arr). Then, we’re saying that, if the array is of length 1 or less, the array is returned. Next, we’re defining the element in the i^th position of an array of length n as the key.

We’re putting constraints on the computation so that j is only operated on when it’s greater than or equal to index 0. J is considered the value to the left of whichever item we’re looking at, as per j = i -1. If its value is greater than the key, its position is shifted to the right.

The final line, arr[j+1] = key, dictates that the value to the right of this j value becomes the new key. Therefore, the rest of the numbers are swapped as necessary. This process then continues from the beginning, until all numbers are correctly sorted.

Insertion Sort in Python: Implementation

Let’s see how this is implemented in Python within the Spyder environment. We’ll use the same array as previously to illustrate this clearly. See the implemented code below:

A key takeaway is that indentation is critical when using Python. If indentation is not used properly, you’ll receive an error message that looks like something below.

Best and Worst Use Cases of Insertion Sort

While insertion sort is useful for many purposes, like with any algorithm, it has its best and worst cases. This is mostly down to time and space complexity.

Time Complexity with Insertion Sort

Time complexity in each case can be described in the following table:

You can see that, in the best case, the time complexity is equal to O(n). This means that no sorting is required, as the array is already sorted. Because the algorithm has to check each value in sequence before it can determine the array is sorted, the time complexity is linear. That is, the complexity is linearly proportional to the size of the input.

In the average and worst cases, however, the complexity is equal to O(n2). An average case would be where the elements in the array are jumbled, neither ascending nor descending. In the worst case, the elements would need to be sorted in reverse.

This is because they’re already in ascending or descending order, and you require the opposite order. This type of complexity is known as quadratic time because it’s dependent on n2. For example, if the size of the input is 4, the number of operations would be 16.

Space Complexity with Insertion Sort

The other kind of complexity is space complexity. This refers to the amount of memory space required to run the algorithm. A complexity of O(1) means that the amount of memory required is constant, irrespective of input size.

This is true in the case of insertion sort because you are only using one temporary variable with each operation. In other words, only one value is sorted at one time, so the memory use is constant.

It should be noted that insertion sort is considered a stable algorithm, meaning the relative order of elements with equal values is preserved. This is helpful if you need to preserve the order of specific elements, or need to sort arrays that are already partially sorted. This is because elements are not swapped with the key if they’re equivalent to it.

Wrapping Up

We’ve covered what insertion sort is and when it’s appropriate to use. As well as this, we’ve considered its time and space complexity and shown its code representation and implementation in Python. If you’re looking to sort a relatively small array, particularly one where some elements are already sorted, insertion sort is one of the best methods to use.

Up Next

• The Algorithm to Solve Rubik’s Cube – Cracked and Explained
• How to Drop Columns in Pandas
• What’s the Difference Between a Frontend and Backend Developer?

The image featured at the top of this post is ©BEST-BACKGROUNDS/Shutterstock.com.