Insertion sort example step by step

1. Overview

In this article, we will learn to implement Insertion sort step by step with a relevant example. You can find more sorting algorithms here.

2. Insertion sort

Insertion sort partitions the provided array into sorted and unsorted partitions. It then grows the sorted partition from left to right, that is front of the array.

2.1. Insertion sort step by step

Step 1: Insertion sort works by considering the element at position zero as the sorted partition. This sorted partition is of length one and by default sorted since there is only one element.

Step 2: Then we set the first unsorted index field to index 1. So from index 1 till the end of the array is an unsorted partition.

Step 3: Take the first element in the unsorted partition as the key to be sorted. We compare and insert this key element into the sorted partition.

Step 4: Compare the key with the values in the sorted partition. We traverse the sorted partition from right to left and we look for a value which is less than or equal to the one we’re trying to insert. Once we found that value, we got the correct insertion position.

We shift the values in the sorted partition to the right if the value is greater than the element we’re trying to insert.

For example, we compare 30 at the first index of the unsorted partition with 25 at the sorted partition. Since 30 is already greater than 25, we just increment the sorted partition size by 1.

Again, we take -10 at the first index of the unsorted partition and compare it with values in the sorted partition from right to left. First, we compare with 30 and since it is greater than -10, we copy it to the next index 2.

Next, we compare -10 with 25 and copy 25 to the next index 1. i.e., we keep shifting elements to the right.

Now, we reached the front of the array and copy the element to the index 0.

3. Insertion sort example

Following is the Java implementation of the insertion sort:

    private static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            
            while (j >= 0 && arr[j] > key) {
                arr[j+1] = arr[j];
                j = j - 1;
            }
            arr[j+1] = key;
            System.out.print("Iteration " + i + ":");
            for (int k = 0; k < arr.length; k++) {
                System.out.print(arr[k] + " ");
            }
            System.out.println("");
        }
    }

If you execute the above code, it prints the following output on the console:

Iteration 1:25 30 -10 6 50 0 -22 
Iteration 2:-10 25 30 6 50 0 -22 
Iteration 3:-10 6 25 30 50 0 -22 
Iteration 4:-10 6 25 30 50 0 -22 
Iteration 5:-10 0 6 25 30 50 -22 
Iteration 6:-22 -10 0 6 25 30 50 

4. Conclusion

To sum up, we have learned to implement insertion sort step by step with an example.