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,

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:

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:

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

Computer Fundamentals Quiz

« Previous Tutorial Next Tutorial »

Liked this post? Share it!