Interview Kickstart has enabled over 3500 engineers to uplevel.
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:
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.
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.
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, 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 as a variable, say “key,” and compare it to the only element in the sorted subarray, arr.
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, 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.
Getting the hang of it? Here’s the pseudocode for insertion sort. Go ahead and implement it in a programming language of your choice.
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.
Here’s a brief of what we’ve done in the code:
Array before sorting :
5 3 4 1 6 2
Array after sorting :
1 2 3 4 5 6
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.
Its time complexity is quadratic, so it is not efficient for large data sets.
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).
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!
Article contributed by Shivam Gupta