Home

 › 

Articles

 › 

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

Insertion Sort

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 0th 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:

1014571

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.

1014571

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.

5101471

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.

5710141

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.

5710141

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:

1571014

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 ith 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:

insertion sort
Implementing insertion sort in Python.

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.

insertion sort
Receiving an error message.

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:

CaseTime Complexity
BestO(n)
AverageO(n2)
WorstO(n2)

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

Frequently Asked Questions

What is insertion sort?

Insertion sort is an algorithm that can be used to sort data sets into ascending or descending order. It’s similar to how you would sort a deck of cards in your hands, in that the first element is considered sorted.

Each subsequent element is then compared to the first element and placed in the correct position, either leaving it where it is or moving it one position to the right. This is repeated for each element, and then the process is continued from the start until all elements are sorted.

When should you use insertion sort?

Insertion sort is best used for small data sets and those where the values are already partially sorted.

What programming languages can implement insertion sort?

A lot of programming languages can implement insertion sort, including C, C++, C#, Java, Javascript, PHP, and Python.

What are the advantages of insertion sort?

The advantages of insertion sort are that it’s simple, the relative order of the keys doesn’t change, its efficient for small data sets, and the fact that it can sort a list while it’s being received.

How is insertion sort optimized?

Insertion sort is optimized by creating a stored subarray, where sorted values are temporarily stored. This means that a full swap of the array elements during each iteration isn’t required, as elements are swapped one at a time.

How many iterations are there in insertion sort?

With an array of length n, it takes n-1 iterations to sort the entire array.

How can insertion sort be modified?

Insertion sort can be modified by using binary insertion sort. This is similar to insertion sort in that it’s a stable algorithm, but it reduces the number of comparisons that need to be made.

The time complexity is reduced from O(n) to O(log n) because it uses binary search rather than linear search. Each value is compared to the values in the sorted subarray to determine which value is just greater than the selected value. This shortens the number of operations.

 

What are the drawbacks of insertion sort?

Insertion sort isn’t appropriate for particularly large data sets, since the time complexity in the average and worst case is quadratic.

What are the alternatives to insertion sort?

With large and jumbled data sets, more appropriate alternatives are quick sort, merge sort, or heap sort.

Is insertion sort a stable algorithm?

Yes, insertion sort is considered a stable sorting algorithm, because elements are left unchanged if they’re equal to the key. The order of elements is also preserved if they’re equivalent to each other.

To top