Sorting Algorithms Studies: Insertion Sort

Continuing the Sorting Algorithms Studies series, let’s talk about Insertion Sort. Basically, this algorithm takes inspiration from the way that you would normally sort a hand of shuffled cards.

Explanation

This algorithm works by, starting at the second element of the list, repeatedly comparing the current value with the previous value, and swapping them if the previous value is higher than the current value; or, if the sorting is being done in decrescent order, if the previous value is lower than the current value. Having provided the clarifications, from now on this article will focus on the crescent order implementation.

Besides doing that with the previous element, if there was a swap, before going ahead and making the comparisons amongst the next elements, it goes retroactively, verifying if the swapped element is in the right place. If it isn’t, continues swapping it with the previous elements until it is. After that, the algorithm resumes the comparisons with the next elements.

Structure

It is comprised by two nested loops:

  • The outer one loops amongst the numbers that comprise the range between 1 and the size of the array, minus 1. Example: if the array has size 5, the outer loop will loop from 1 to 4. Let’s call the number of the outer loop x.
  • The inner loop is the one that actually makes the comparisons and swaps. It loops amongst the numbers that comprise the range between x and 0, not including zero itself. Let’s call the number of the inner loop y. But, although the loop is comprised by these values, an inner loop iteration will only be executed if the element in the y index is lower than the element in the y - 1 index. Example: if the array has size 5, the inner loop will loop from 2 to 0 on the first outer loop, 3 to 0 in the second outer loop, and so on, always checking the condition stated above.
  • For each y in the inner loop, as the condition above was already checked as a requirement for the loop iteration to be valid, all that is left is to swap the element in the index y with the one in the index y - 1.

Also, there is an Insertion Sort implementation with a minor optimization. Instead of continuously swapping elements, for each outer loop, it stores the value of the element in the x index in an auxiliary variable. Then, it keeps assigning the value in the index y to the y + 1 index as long as y is bigger or equal to zero and the value in the index y is greater than the value in the auxiliary variable. Finally, when the inner loop is finished, the auxiliary variable value is assigned to the y + 1 index.

Code

This is the implementation of Insertion Sort in Python. It may look slighter more complex than the usual Insertion Sort implementation, but that’s because I’ll to provide codes that work both for the crescent and decrescent sorting.

And this is the implementation of optimized Insertion Sort in Python. Again, this codes works both for the crescent and decrescent sorting.

Step By Step Execution

The execution below will illustrate the steps of a crescent ordering insertion sort (optimized) execution.

The input data is:

a = [3, 1, 5, 4, 2]
a_size = 5

Array - Initial

Array - Initial. Image extracted from https://algorithm-visualizer.org/

The outer loop will define the x range. From the input data, we can assume that x will range from 1 to (a_size - 1) => 1 to (5 - 1) => 1 to 4.

With the first outer loop, having x = 1, we store our current value, which is the element in the x index, in current. For this iteration, current = 1. Also, we know that y will range from 0 to (x - 1) => 0 to (1 - 1) => 0 to 0, and the loop will exists as long as the current element of the outer loop is smaller than the element on the y position of the array.

This is the inner loop iteration for the first outer loop iteration:

  • y = 0 => 1 < a[y] => 1 < a[0] => 1 < 3 => Set a[y + 1] to a[y] => Set a[1] to 3 => [3, 3, 5, 4, 2]

Set a[1] to 3

Set a[1] to 3. Images extracted from https://algorithm-visualizer.org/

With the end of the inner loop iterations, the current outer loop iteration is finished by setting the current value to the array position that is posterior to the y position (e.g.: y + 1), which translates as: Set a[y + 1] to 1 => Set a[-1 + 1] to 1 => Set a[0] to 1 => [1, 3, 5, 4, 2]

Set a[0] to 1

Set a[0] to 1. Images extracted from https://algorithm-visualizer.org/

With the second outer loop, having x = 2, we store our current value, which is the element in the x index, in current. For this iteration, current = 5. Also, we know that y will range from (x - 1) to 0 => (2 - 1) to 0 => 1 to 0, and the loop will exists as long as the current element of the outer loop is smaller than the element on the y position of the array.

This is the inner loop iteration for the second outer loop iteration:

  • y = 1 => 5 < a[y] => 5 < a[1] => 5 < 3 => End of the inner loop

With the end of the inner loop iterations, the current outer loop iteration is finished by setting the current value to the array position that is posterior to the y position (e.g.: y + 1), which translates as: Set a[y + 1] to 5 => Set a[1 + 1] to 5 => Set a[2] to 5 => [1, 3, 5, 4, 2]

Set a[0] to 1

Set a[0] to 1. Images extracted from https://algorithm-visualizer.org/

With the third outer loop, having x = 3, we store our current value, which is the element in the x index, in current. For this iteration, current = 4. Also, we know that y will range from (x - 1) to 0 => (3 - 1) to 0 => 2 to 0, and the loop will exists as long as the current element of the outer loop is smaller than the element on the y position of the array.

These are the inner loop iterations for the third outer loop iteration:

  • y = 2 => 4 < a[y] => 4 < a[2] => 4 < 5 => Set a[y + 1] to a[y] => Set a[3] to 5 => [1, 3, 5, 5, 2]

Set a[3] to 5

Set a[3] to 5. Images extracted from https://algorithm-visualizer.org/

  • y = 1 => 4 < a[y] => 4 < a[1] => 4 < 3 => End of the inner loop

With the end of the inner loop iterations, the current outer loop iteration is finished by setting the current value to the array position that is posterior to the y position (e.g.: y + 1), which translates as: Set a[y + 1] to 4 => Set a[1 + 1] to 4 => Set a[2] to 4 => [1, 3, 4, 5, 2]

Set a[2] to 4

Set a[2] to 4. Images extracted from https://algorithm-visualizer.org/

With the fourth outer loop, having x = 4, we store our current value, which is the element in the x index, in current. For this iteration, current = 2. Also, we know that y will range from (x - 1) to 0 => (4 - 1) to 0 => 3 to 0, and the loop will exists as long as the current element of the outer loop is smaller than the element on the y position of the array.

These are the inner loop iterations for the third outer loop iteration:

  • y = 3 => 2 < a[y] => 2 < a[3] => 2 < 5 => Set a[y + 1] to a[y] => Set a[4] to 5 => [1, 3, 4, 5, 5]

Set a[4] to 5

Set a[4] to 5. Images extracted from https://algorithm-visualizer.org/

  • y = 2 => 2 < a[y] => 2 < a[2] => 2 < 4 => Set a[y + 1] to a[y] => Set a[3] to 4 => [1, 3, 4, 4, 5]

Set a[3] to 4

Set a[3] to 4. Images extracted from https://algorithm-visualizer.org/

  • y = 1 => 2 < a[y] => 2 < a[1] => 2 < 3 => Set a[y + 1] to a[y] => Set a[3] to 3 => [1, 3, 3, 4, 5]

Set a[2] to 3

Set a[2] to 3. Images extracted from https://algorithm-visualizer.org/

  • y = 0 => 2 < a[y] => 2 < a[0] => 2 < 1 => End of the inner loop

With the end of the inner loop iterations, the current outer loop iteration is finished by setting the current value to the array position that is posterior to the y position (e.g.: y + 1), which translates as: Set a[y + 1] to 2 => Set a[0 + 1] to 2 => Set a[1] to 2 => [1, 2, 3, 4, 5]

Set a[1] to 2

Set a[1] to 2. Images extracted from https://algorithm-visualizer.org/

At the end of the final outer loop iteration, the array is ordered.

Array - Final

Array - Final. Image extracted from https://algorithm-visualizer.org/

Complexity

Worst-case performance: O(n²)

Best-case performance: O(n)

Average performance: O(n²)

Space complexity 1: O(n)

Auxiliary space 2: O(2) for the normal implementation; O(2) for the optimized implementation. 3

Benchmark

As the posts from the Sorting Algorithms Studies are posted, I’ll benchmark the algorithms against each other. For now, there’s only Bubble Sort and Insertion Sort to be shown.

Sorting 1000 different arrays with 1000 randomly sorted elements
Algorithm Average Time Spent (seconds)
Insertion Sort Optimized - Decrescent 0.0736674513
Insertion Sort Optimized - Crescent 0.0753681884
Insertion Sort - Decrescent 0.1312314609
Insertion Sort - Crescent 0.1372412237
Bubble Sort - Decrescent 0.1544748926
Bubble Sort Optimized - Decrescent 0.1566215120
Bubble Sort - Crescent 0.1582083573
Bubble Sort Optimized - Crescent 0.1596853969

Sorting 1000 different arrays with 1000 elements in ascending order
Algorithm Average Time Spent (seconds)
Bubble Sort Optimized - Crescent 0.0001734812
Insertion Sort - Crescent 0.0002234063
Insertion Sort Optimized - Crescent 0.0003296916
Bubble Sort - Crescent 0.0839870924
Insertion Sort Optimized - Decrescent 0.1450735179
Bubble Sort - Decrescent 0.2211828375
Bubble Sort Optimized - Decrescent 0.2260213672
Insertion Sort - Decrescent 0.2700778754

Sorting 1000 different arrays with 1000 elements in descending order
Algorithm Average Time Spent (seconds)
Bubble Sort Optimized - Decrescent 0.0002013480
Insertion Sort - Decrescent 0.0002713254
Insertion Sort Optimized - Decrescent 0.0003897878
Bubble Sort - Decrescent 0.0919957102
Insertion Sort Optimized - Crescent 0.1607460458
Bubble Sort - Crescent 0.2491307684
Bubble Sort Optimized - Crescent 0.2533746003
Insertion Sort - Crescent 0.2929840205

Wrapping Up

Insertion Sort is a simple algorithm, one that we use daily more than we realize. As the Bubble Sort, it doesn’t performs well, but it may be enough for some scenarios, like when you have really small lists.

Stay tuned for the next chapters of this series!

  1. Auxiliary Space + Input space

  2. Extra or temporary space used by the algorithm during it's execution.

  3. Python's way of swapping two values dismisses the need of a temp variable to make the swap of values. Because of that, there normal implementation in Python uses O(1) auxiliary space. The optimized implementation still uses O(2) auxiliary space.