Insertion Sort

Overview

Let’s learn about insertion sort with an example. Look at the figure below.

There are four balls of different sizes. Suppose we are given the task to sort the balls according to their size, i.e., the smallest ball first and the largest ball last. Let’s sort it using insertion sort.

First round

In the first round, the first ball is picked.

Look behind. There’s no ball behind the blue ball, so the first round is complete. The order after the first round remains unchanged.

Second round

In the second round, the second ball (the green ball) is picked. Look behind. There is a blue ball.

• Compare the size of the blue ball with the green ball. The green ball is smaller. Move the blue ball one place forward to leave an empty

...