The algorithm starts at index position 1.

The first comparison is executed. The insertion sort algorithm starts at index 1 and compares it to the index before, which in this case is index 0.

Considering 7 is not less than 4, the values will remain in their current positions. Since the algorithm reached index 0, it needs to increment the current position to start the next comparison. It is now at index 2. The algorithm starts the comparison between the value at index 2 and the value at index 1.

Since the value at index 2 is less than the value at index 1, the algorithm is going to swap the values at those indexes. The index is decremented by 1, so it’s back at index 1 now. It compares the value at index 1 with the value at index 0.

Since the value at index 1 is less than the value at index 0, it’s going to swap those two values. The insertion sort algorithm has reached the end of the comparison cycle. It increments the starting index value from 2 to 3.

Since the value at index 3 was less than the value at index 2, it swaps the values. It decrements the index from 3 to 2 and starts the comparison with index 1.

Since the value at index 2 is less than the value at index 1, the algorithm swaps the two values. It decrements the index from 2 to 1 and compares that value with the value at index 0.

Since the value at index 1 is not smaller than the value at index 0, the values stay in their current spots. The starting index value is incremented to 4.

The algorithm starts its comparison between the values at index 4 and index 3.

Since the value at index 4 is not less than the value at index 3, no swap occurs. It’s also worth mentioning that it is known that the values before index 3 are smaller than the value at index 3; there is no reason to compare the value at index 4 with those values since they’re already guaranteed to be smaller than the value at index 3. The starting index is incremented from 4 to 5.

The algorithm compares the value at index 5 with the value at index 4.

Since the value at index 5 is less than the value at index 4, the two values are swapped. The index is decremented and the value at index 4 is compared to the value at index 3.

Since the value at index 4 is less than the value at index 3, the two values are swapped, and the index is decremented from 4 to 3. The value at index 3 is compared to the value at index 2.

Since the value at index 3 is larger than the value at index 2, the values are not swapped. The algorithm has reached the end and the array is sorted:

1, 2, 4, 5, 7, 8.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.

My Book: An Illustrative Introduction to Algorithms

This book was written to fill the gap that exists when Computer Science students and programmers, attempt to learn and analyze the different algorithms that currently exist. I took a course on Algorithms and was disappointed in the type of material that’s currently available. There are two types of books that I kept running into:

• First, the overly complex book. This book seems like it’s designed for people that are already fluent in the topics and wanted a more detailed and mathematical approach to algorithms.
• Second, the overly simple book. A basic introduction to algorithms. This is a high-level overview of some algorithms, and most complex algorithms are not mentioned. After completion, the person is still incapable of showing how the algorithm runs when a problem is presented.

This book is designed for undergraduate upper-class students and programmers that want to expand their horizon. It can be used as a supplementary book alongside the complex book. Readers will gain the knowledge necessary to solve those mathematically intensive algorithmic problems that were presented in the complex book. Each chapter consists of a brief description of how the algorithm works followed by a detailed example or two. No steps are skipped during the traversal process. The reader is presented with a clear, simplified approach to solving the algorithm that the chapter is dedicated to.

Each chapter follows a natural progression from the previous chapter. If certain algorithms rely heavily on prior knowledge, the previous chapter covers that topic. For example, Kruskal’s algorithm relies heavily on prior knowledge of Minimum Spanning Trees and Greedy Algorithms. Each of those topics receives a chapter of its own.

Available now at Amazon.com