Intro to Insertion Sort Algorithm With Code Examples

Insertion sort is a simple sorting algorithm and it is used to sort an array by iteratively inserting elements into a sorted subarray that results in a final sorted array. Insertion sort starts iteration from the second element of the array and compares each element with the ones before it. If the element being compared is smaller than the one before it, then the algorithm swaps the two elements (and keeps swapping with the next element before it after the last swap) until the smaller element is in its correct sorted position.

Given below is the step by step explanation of how insertion sort works

1. Start with the second element of the array, and compare it with the first element. If the second element is smaller, swap the two elements.

2. After that, move to the third element and compare the third element with the second element. If the third element is smaller than the second element, then swap it with the second element, and then compare the new second element with the first element. If the second element is smaller than the first, swap them.

3. Continue this process for all remaining elements in the array, comparing each element with the ones before it and swapping them if necessary to keep the array sorted.

4. Once all elements have been sorted, the array becomes sorted in ascending order.

   
   

For better clarity, let us look at the below array and see how the insertion sort algorithm would sort the array, Example array: [5, 2, 4, 6, 1, 3], and the steps to sort are as below –

Step 1: [2, 5, 4, 6, 1, 3]
Step 2: [2, 4, 5, 6, 1, 3]
Step 3: [2, 4, 5, 6, 1, 3]
Step 4: [1, 2, 4, 5, 6, 3]
Step 5: [1, 2, 3, 4, 5, 6]

In this example, the algorithm first compares 2 with 5 and swaps both since 2 is less than 5, this results in a partially sorted array that looks like [2, 5, 4, 6, 1, 3]. Algorithm then compares 4 with 5, and since 4 is smaller, it swaps 4 with 5, resulting further partially sorted array [2, 4, 5, 6, 1, 3]. The algorithm continues in this way and keeps on swapping elements till the time array is fully sorted.

Given below is the pseudo-code for insertion sort, you can pick it up and implement in any programming language –

for j = 2 to n:
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key:
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key

In the above pseudocode, A is the array that we want to sort with insertion sort, n is the length of the array, and “key" is the current element (temporary variable to store current element), and i is the variable that holds the index of the element before the current element gets sorted.

The outer for loop in the above pseudo-code iterates over every element in the array, starting from the second element. The inner loop compares the current element with the ones before it and swaps them if necessary to keep the array sorted. The variable key keeps track of the current element being sorted, and the variable i keeps track of the index of the element before it.

Stability: Is Insertion Sort Stable?

Insertion sort is a stable sorting algorithm. Well, what do we really mean by an algorithm being stable? Okay, in short, a sorting algorithm is called a stable algorithm if it preserves the relative order of equal elements in the input array. Example: If 5 appears twice in the array, then left most 5 in the sorted array should be the 5 that occurred first in the original array.

In insertion sort, when two elements have the same value, the algorithm always chooses the one that comes first in the input array and moves the other one to a position after it. Therefore, the relative order of equal elements is preserved, and insertion sort is a stable sorting algorithm.

This property of stability is particularly useful in cases where the input data has some inherent order, and we want to sort it based on some other criteria while maintaining the original order of equal elements. For example, when sorting a list of students by their grades, if two or more students have the same grade, we might want to maintain the order in which they appear in the original list. In such cases, we can use a stable sorting algorithm like insertion sort to achieve the desired result.

The time complexity of Insertion Sort

We typically look at time complexity in best, worse, and average cases. when it comes to insertion sort, the time complexity of it is O(n^2) in the worst and average cases, where n is the number of elements in the array. This essentially means that the time it takes for the algorithm to sort the array increases quadratically with the size of the array.

The worst case for insertion sort occurs when the starting array is in reverse order. This is because each element in the leftover unsorted array is required to be compared to every element in the already sorted array to find the correct position for the element. This results in n comparisons for the first element, n-1 for the second element, n-2 for the third element, and so on, for a total of (n*(n-1))/2 comparisons, which is O(n^2).

But why is the average case time complexity the same as the worst case? The average case time complexity of insertion sort is also O(n^2) because the algorithm has to make the same number of comparisons regardless of the initial order of the array.

When compared to other algorithms like bubble sort and selection sort that have the same worst-case time complexity, insertion sort can end up being faster since it is more efficient when the input array is already partially sorted.

In addition, insertion sort has a small constant factor, which means it can be faster than other algorithms for small input sizes.

In general, insertion sort is a simple and efficient algorithm for sorting small arrays, but it becomes less practical for larger arrays because its time complexity grows quickly with the size of the array.

For larger arrays, more advanced algorithms, such as merge sort or quicksort, are typically used because they have better worst-case and average-case time complexity.

You should also look at binary insertion sort to improve the insertion sort algorithm time complexity further.

Space Complexity of Insertion Sort

Insertion sort space complexity is O(1), which essentially means that the extra memory needed to accomplish the sorting doesn’t depend on the size of the original input array.

The only extra space used by the algorithm is for temporary variables, such as the “key" variable used in the above pseudo-code example. However, these temporary variables like “key” have a constant size that does not depend on the size of the input array, so the additional space consumption to the overall space complexity of the algorithm is negligible.

Given the above, insertion sort becomes a good option for sorting arrays where memory usage is a critical factor. The situations, where memory is not a problem, and array size is huge, then you should opt for other algorithms like merge sort or quicksort – they would behave much better on time complexity.

Insertion Sort program in C

If you want to write a program to implement insertion sort in C programming language, below is a quick reference code for you.

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // Move elements of arr[0..i-1], that are
        // greater than key, to one position ahead
        // of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

In the above code, the function insertionSort takes an array arr of integers and the size of array n as two arguments. The algorithm code then iterates through the array from index 1 to n-1, also and for each element at index i, it compares it with the previous elements in the array (from index i-1 down to 0) and moves them one position to the right until the correct position for the current element is found.

The variable named “key” is used to temporarily store the current element and the variable “j” is used to keep track of the position in the sorted portion of the array where the current element should be inserted.

At the end of each iteration, the current element is inserted into the correct position in the sorted portion of the array, by placing it after the last element that is smaller than it. The loop terminates when the correct position for the current element is found, or when the beginning of the array is reached (j < 0).

After the loop completes, the array is sorted in ascending order.

Insertion Sort program in Java

If you want to write a program to implement insertion sort in Java programming language, below is a quick reference for you.

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

Insertion Sort program in Python

If you want to write a program to implement insertion sort in Python programming language, below is a quick reference for you.

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Insertion Sort program in Javascript

If you want to write a program to implement insertion sort in JavaScript, below is a quick reference for you.

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

Quick Recap of Insertion Sort: Key Features

This brings us to the end of this tutorial, but before we move on, given below is a quick recap of everything you need to know about insertion sort.

• Insertion sort doesn’t require additional space, and for that reason, it is considered to be an in-place sorting algorithm.
• Simple and intuitive to understand, even for beginners.
• Works great on small and partially sorted arrays, with worst-case time complexity of O(n^2).
• Stable algorithm – Preserves relative order of equal elements in the input array.
• You can further improve the performance of insertion sort by implementing binary search to efficiently find the correct position of the current element.
• Insertion sort is not suited for large arrays or arrays which are totally random in order.
• If your array continuously keeps getting additional elements in the end (live feed), insertion sort is a good option since it picks elements left to right one by one.

Hope you enjoyed the article, if so, please do share it with your friends in the University and over social media.

Also published here.