Insertion Sort Algorithm and Example

In this article, you will learn about how an insertion sort actually works. You will understand it with the help of a step-by-step algorithm and an example. But before we get started, let's first discuss what the term "insertion sort" means.

What is insertion sorting?

It operates in a manner analogous to how you would sort the playing cards that you have in your hand. That is to say, you select and then pick up the card (from the beginning), and then you place it one at a time in a sorted order.

Insertion Sort Algorithm

The algorithm for using insertion sort to put an array in ascending order is as follows:

1. Beginning with arr[1] and ending with arr[n].
2. Compare the current element (key) to the element present and its predecessor.
   • Here, at first execution, the current element will be at arr[1] (the second element from the array).
   • At the second execution, the current element will be at arr[2] (the third element from the array).
   • And so on.
3. If the current element is smaller than its predecessor,
4. Then compare it to the elements present before the index of the current element.
5. Move the greater elements one index up to create space for the swapped element.

Steps 3, 4, and 5 of the algorithm are repeated with the following iterations:

8   6   4
6   8   4
4   6   8

As you can see,

• At first iteration, the key element 6 is smaller than its predecessor (that is, the element present before the index of the key element).
• So the greater element (8) gets moved one index up and creates a space.
• That is, 8 is moved to the position where 6 was previously.
• And the current index of 8 is available for 6 to get a place.
• So 6 gets placed on the previous index of 8.
• And the key element 4 is smaller than its predecessor at the second interation.
• That is, this time, 4 is smaller than both of its predecessor elements.
• That is 6 and 8.
• So these two elements moved up one index.
• That is, 8 goes to the index where 4 was present, and 6 goes to the index where 8 was present.
• And finally, 4 is placed at the index where 6 was present.
• In this way, the insertion sort works.

In insertion sort, each element is placed one by one to the left (if necessary). That is, from the first to the last element, we have to decide the correct place for each element one by one and arrange the given array in ascending order as per the insertion sort technique.

Insertion Sort Example

For example, if the user has supplied any array that contains elements such as 28; 16; 5; and 11; Therefore, here is a step-by-step sorting of the given array:

• 16 28 5 11 0
• 5 16 28 11 0
• 5 11 16 28 0
• 0 5 11 16 28

That is, the sorted array you will get is 0 5 11 16 28.

Let's take another example. Assume the user supplied an array whose elements are 1, 10, 2, 9, 3, 8, 4, 7, 5, and 6. Therefore, here is the step-by-step list of the array after each sort:

• 1 2 10 9 3 8 4 7 5 6
• 1 2 9 10 3 8 4 7 5 6
• 1 2 3 9 10 8 4 7 5 6
• 1 2 3 8 9 10 4 7 5 6
• 1 2 3 4 8 9 10 7 5 6
• 1 2 3 4 7 8 9 10 5 6
• 1 2 3 4 5 7 8 9 10 6
• 1 2 3 4 5 6 7 8 9 10

As you can see, in the step-by-step array after each sort, the first step gets skipped because we already have the first and second elements of the array in ascending order.

Programs Created on Insertion Sort

• Insertion Sort in C
• Insertion Sort in C++
• Insertion Sort in Java

Computer Fundamentals Quiz