A Beginner's Guide to Insertion Sort

Insertion sort is one of those algorithms that looks simple but feels confusing when you first come across it.

As a beginner, I struggled to understand how it actually works. This article walks through insertion sort step-by-step, making sure you don’t get stuck in the places I did.

ALGORITHM

• It works on the principle of picking up an element and “INSERTING“ it in the right place, hence the name insertion sort.

• we divide the array into two parts

  1. The left sorted part

  2. The right unsorted part

• The idea is to create space for the correct element by shifting larger elements one position to the right.

• Here is the basic working of the algorithm:

  1. Assume arr[0] is already sorted.

  2. iterate through the array while storing the current element as ‘key‘.

  3. Compare key with elements to its left.

  4. Shift bigger elements one step right.

  5. Drop key in the gap we just created.

  6. Move to the next index. Repeat.

DRY-RUN EXAMPLE

Let us consider an array [14,9,15,12,6,8,13].

We will be sorting this using insertion sort.

The highlighted part represents the sorted part of the array.

1. Step-0

   • 14 9 15 12 6 8 13

   • we assume that a[0] i.e. 14 is in the correct position

2. Step-1 :

   • i = 1, key = 9

   • compare key with elements to the left.

   • it is smaller than 14, hence we shift 14 by one place to the right and insert 9 in its position.

   • 9 14 15 12 6 8 13

3. Step-2:

   • i = 2, key = 15

   • compare 15 with elements to its left

   • no changes are to be made

   • 9 14 15 12 6 8 13

4. Step-3:

   • i = 3, key = 12

   • compare 12 with elements in the sorted part.

   • 12 < 15 and 12 < 14, hence we place it in the correct place and shift 14 and 15 by one place each.

   • 9 12 14 15 6 8 13

5. Step-4:

   • i = 4, key = 6

   • compare key with elements to its left.

   • 6 < 15, 6 < 14, 6 < 12, 6 < 9, hence we shift all these by one place each and insert key in the void created.

   • 6 9 12 14 15 8 13

6. Step-5:

   • i = 5, key = 8

   • compare key with elements to its left.

   • 8 < 15, 8 < 14, 8 < 12, 8 < 9, hence we shift all these one step to the right and insert key in the void created.

   • 6 8 9 12 14 15 13

7. Step-6:

   • i = 6, key = 13

   • compare key with elements to its left.

   • 13 < 15, 13 < 14, hence we shift all others by one place each and insert key in the void created.

   • 6 8 9 12 13 14 15

The array achieved is sorted in the ascending order.

CODE IMPLEMENTATION

public static void insertionSort(int[] arr){
    int key, j;
    for(int i=1;i<arr.length;i++){
        key = arr[i];
        j = i-1;
        while(j>=0 && arr[j]>key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

• The outer loop starts from 1 because we have already assumed that the first element in sorted by default.

• The inner loop iterates through the ‘left sorted part‘ of the array and looks for elements greater than ‘key‘. When we find something, perform the shift of other elements one step to the right.

• We finally insert key in the gap just created.

TIME COMPLEXITY

1. Worst Case

• The array is reverse sorted.

• The total number of operations is

  • 1 + 2 + 3 + … + (n-1)

  • which is equal to 1 + 2 + 3 + … + (n-1) = n(n-1)/2

  • which corresponds to n²/2 + n/2

  • Upon ignoring constants, we get a time complexity of O(n²).

2. Average Case

• The array is randomly sorted.

• Very much like the worst case, we happen to get a quadratic time complexity for average case as well.

• Thus, Time Complexity : O(n²)

3. Best Case

• The array is already sorted.

• Here we will not need to do any shifting or insertions as the array is sorted already.

• Hence the inner loop never runs, and the outer one runs (n-1) times.

• Upon ignoring constants, we get a Linear Time Complexity: O(n).

SPACE COMPLEXITY

Consider the following points:

• We do not create any new arrays or perform recursion.

• Memory usage does not increase with input size.

• Constant number of variables corresponds to constant space.

Hence, the space complexity of insertion sort happens to be O(1).

CONCLUSION

More than speed, insertion sort is about the idea of how sorting actually works. Tracing each comparison and shift helps in building up an intuition about arrays. A confident hold on the working of insertion sort gets you in a great position to understand why faster algorithms (like merge sort and quick sort) exist and how they improve on this idea.