Sorting algorithms are a must-know for any software developer. And if you are preparing for a coding interview, brushing up on your sorting algorithms is crucial.

Insertion sort is one such sorting algorithm, which has great potential to help you answer complex data structure questions asked in tech interviews.

In this article, we cover everything you need to know about insertion sort, including:

• What Is Insertion Sort?
• How Insertion Sort Works
• Insertion Sort Algorithm
• Insertion Sort Pseudocode
• Insertion Sort Code
• Insertion Sort Complexity
• Advantages of Insertion Sort
• Disadvantages of Insertion Sort
• Insertion Sort FAQs

What Is Insertion Sort?

Insertion sort is a simple and intuitive sorting algorithm in which we build the sorted array using one element at a time. It is easy to implement and is quite efficient for small sets of data, especially for substantially sorted data. It is flexible — it is useful in scenarios where all the array elements are not available in the beginning.

You may have used this sorting method unknowingly at some point in your life. Insertion sort is also known as “card player” sort. If you’ve ever played a game of cards, chances are you have used some form of insertion sort to arrange the cards in your hand in a strategic order. 

How Insertion Sort Works

Insertion sort works by continually inserting each element from an unsorted subarray into a sorted subarray (hence the name “insertion” sort).

It virtually splits the array into a sorted and an unsorted subarray. Initially, the sorted subarray consists of a single element — the first element — and the rest of the elements form the unsorted subarray. 

Then, we iterate over the unsorted subarray elements, remove them from the unsorted subarray, and place them at the correct position in the sorted subarray. We repeat this until no element remains in the unsorted subarray, and we get the sorted array.

Insertion Sort Algorithm

1. Consider the first element to be a sorted subarray and the rest as an unsorted subarray
2. Sequentially iterate over the unsorted elements of the array and move them to the sorted subarray.
3. For each unsorted element, compare the current element with the elements before it
4. If the current element is greater than its preceding element, leave it there, as it is already at the desired position. If not, keep comparing it with the elements before it until:

• A smaller or equal element is found: Insert the current element after it
• All comparisons are made, and no smaller element is found: Insert the current element at the beginning of the array

     5.Repeat the above process for every element of the unsorted subarray until the array is sorted

Let’s take an example to understand better. Suppose we have to sort the following array “arr” of size n = 6.

In the beginning, we can take just the first element, arr[0], as the sorted subarray. As it is the only element in that subarray, the subarray is sorted by nature. We can assume the remaining elements, arr[1...n-1], to be part of the unsorted subarray.

We will store the first element in the unsorted subarray arr[1] as a variable, say “key,” and compare it to the only element in the sorted subarray, arr[0]. 

If the key is greater, we will insert it before the first element, otherwise after it. Now, there are two elements in the sorted subarray and n - 2 elements in the unsorted one.

Again, we will take the first element in the unsorted subarray, arr[2], store it in key, and compare key with the elements to the left of it in the unsorted subarray. Then, we insert it at the position just after the element smaller than or equal to it.

If we don’t find any element smaller than or equal to the key, we will insert it at the beginning of the sorted array.

We will repeat the above process for the remaining elements in the unsorted subarray until the entire array gets sorted.

Insertion Sort Pseudocode

Getting the hang of it? Here’s the pseudocode for insertion sort. Go ahead and implement it in a programming language of your choice.

insertionSort(array A)
for i = 1 to length(A) - 1
    key ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j + 1] ← A[j]
        j ← j - 1
    end while
    A[j + 1] ← key
end for

Insertion Sort Code in C++

We’ve chosen C++ to demonstrate how the code works. You can implement the same in C, Java, Python, or any other programming language you’re comfortable with.

// C++ program to demonstrate insertion sort algorithm
#include 
using namespace std;
 
// Function to sort an array using insertion sort
void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int key = arr[i]; // Storing the current element

        /* We will compare the current element with each element
        on its left until an element smaller than or equal to it
        is found or we reach the beginning of the array */
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        /* Then we insert the current element at the correct
        position in the sorted subarray arr[0...i] */
        arr[j + 1] = key;
    }
}
 
// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << ' ';
    cout << '\n';
}

// Main Function 
int main() {
    int arr[] = {5, 3, 4, 1, 6, 2};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Array before sorting :\n";
    printArray(arr, size);
 
    insertionSort(arr, size);

    cout << "Array after sorting :\n";
    printArray(arr, size);
 
    return 0;
    }

Here’s a brief of what we’ve done in the code:

• We took a randomly arranged array with 6 integers
• We used a variable “key” to store one element of the array during each pass, starting from the second element, a[1]
• Then, using a while loop, we iterated until j became zero (which meant we reached the beginning of the array) ...
• … OR we found an element smaller than or equal to key — then, we inserted the key after that element
• We then stored the next element in key and repeated the same process to get the sorted array

Output

Array before sorting :
5 3 4 1 6 2
Array after sorting :
1 2 3 4 5 6 

Insertion Sort Complexity

Time Complexity

• Best Case: O(n)
  When we initiate insertion sort on an already sorted array, it will only compare each element to its predecessor, thereby requiring n steps to sort the already sorted array of n elements.
  

• Worst Case: O(n2)
  When we initiate insertion sort on a reverse-sorted array, it will insert each element at the beginning of the sorted subarray, making it the worst time complexity of insertion sort. 
  

• Average Case: O(n2)
  When the array elements are in random order, the average running time is O(n2 / 4) = O(n2).
  

Space Complexity

The space complexity of insertion sort is O(1), as we only used a constant amount of additional variables in addition to the input array.

Advantages of Insertion Sort

• On average, insertion performs fewer comparisons than other quadratic sorting algorithms such as bubble sort and selection sort.
• It is a stable sorting algorithm, as it does not change the relative order of elements with equal values.
• It is adaptive, which means it performs a lesser number of operations if a partially sorted array is provided as input, making it efficient.
• It is an in-place algorithm — requires O(1) additional space.
• It is online — it can start sorting the data even if the entire dataset is not available right from the beginning. 

Disadvantages of Insertion Sort

Its time complexity is quadratic, so it is not efficient for large data sets.

Insertion Sort FAQs

Question 1: Is insertion sort a stable algorithm?

Answer: In a stable sorting algorithm, identical elements are sorted in the same order as they appear in the input array. In insertion sort, we insert the current element just after the element smaller than or equal to the current element, i.e., we stop shifting elements when we find an element smaller than or equal to the current element.

Therefore, the order of equal elements in the unsorted array remains the same in the sorted array, making insertion sort stable.

Question 2: Is Insertion sort an in-place sorting algorithm?

Answer: An in-place algorithm is an algorithm that doesn’t use extra space for input manipulation. Its space complexity is usually less than linear.

In Insertion sort, we only use a constant number of extra variables to store the current element, so the space complexity is O(1), making insertion sort an in-place sorting algorithm.

Question 3: What is the average running time of insertion sort?

Answer: For sorting an array of size n through insertion sort, the total number of comparison operations is (n + the number of inversions in the array). The total number of pairs in an array is n * (n - 1) / 2.

Therefore, the maximum number of inversions possible
= n * (n - 1) / 2 (when the array is reverse-sorted)

The minimum of inversions = 0 (when the array is sorted) 

For a randomly arranged array, the average number of inversions
= the average of the maximum number of inversions and minimum number of inversions
= n * (n - 1) / 4

Therefore, the running time of insertion sort averages out to be quadratic, i.e., O(n2).

Are You Ready to Nail Your Next Coding Interview?

Sorting algorithms interview questions feature in almost every coding interview for software developers. If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar. 

As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

----------

Article contributed by Shivam Gupta