Author
Swaminathan Iyer
Product @ Interview Kickstart | Ex Media.net | Business Management - XLRI Jamshedpur. Loves building things and burning pizzas!
Software engineering interviews revolve around tweaking well-known algorithms so that they can be used to solve complex coding problems. Binary insertion sort is one such topic that involves tweaking the well-known insertion sort algorithm. This article is dedicated to analyzing this. We’ll cover:
In a simple insertion sort algorithm, we maintain a sorted and an unsorted subarray of the given array. In each iteration, one value from the unsorted part is picked and is inserted in its correct position in the sorted part. To achieve this, for every element, we iterate over the sorted part of the array to find the position to insert the element.
So, it takes O(N) comparisons and O(N) swaps for inserting one element in the worst case (last element). How can we optimize it?
For a detailed explanation of the insertion sort algorithm, check out “Learn the Insertion Sort Algorithm.â€
Binary insertion sort is a sorting algorithm similar to insertion sort, but instead of using linear search to find the position where the element should be inserted, we use binary search. Thus, we reduce the number of comparisons for inserting one element from O(N) to O(log N).
It is an adaptive algorithm, which means that it works faster when the given array is already substantially sorted, i.e., the current position of the element is near its actual position in the sorted array.
It is a stable sorting algorithm — the elements with the same values appear in the same order in the final array as they were in the initial array.
Binary insertion sort works efficiently when the array has a low number of elements.
While performing quicksort or merge sort, when the subarray’s size becomes small (say <=25 elements), it’s more efficient to use binary insertion sort.
This algorithm is also efficient when the cost of comparison between keys is sufficiently high. For example, if we want to sort an array of strings, the comparison operation of two strings will be high.
In binary insertion sort, we divide the array into two subarrays — sorted and unsorted. The first element of the array is in the sorted subarray, and the rest of the elements are in the unsorted one.
We then iterate from the second element to the last element. For the i-th iteration, we make the current element our “key.†This key is the element that we have to add to our existing sorted subarray.
To do this, we first use binary search on the sorted subarray to find the position of the element that is just greater than our key. Let’s call this position “pos.†We then right shift all elements from position pos to i-1 and then make Array[pos] = key.
We can note that for every i-th iteration, the left part of the array till (i-1) is always sorted.
Suppose we need to sort the following array:
The array now looks like this:
The array now looks like this:
The array now looks like this:
The resulting array is:
We have sorted the given array using binary insertion sort.
Binary insertion sort for array A:
â€
The array after 1 iterations = 6 8 1 5 3
The array after 2 iterations = 1 6 8 5 3
The array after 3 iterations = 1 5 6 8 3
The array after 4 iterations = 1 3 5 6 8
For inserting the i-th element in its correct position in the sorted, finding the position (pos) will take O(log i) steps. However, to insert the element, we need to shift all the elements from pos to i-1. This will take i steps in the worst case (when we have to insert at the starting position).
We make a total of N insertions —  so, the worst-case time complexity of binary insertion sort is O(N^2).
This occurs when the array is initially sorted in descending order.
The best case will be when the element is already in its sorted position. In this case, we don’t have to shift any of the elements; we can insert the element in O(1).
But we are using binary search to find the position where we need to insert. If the element is already in its sorted position, binary search will take (log i) steps. Thus, for the i-th element, we make (log i) operations, so its best-case time complexity is ?(N log N).
This occurs when the array is initially sorted in ascending order.
For average-case time complexity, we assume that the elements of the array are jumbled. Thus, on average, we will need O(i /2) steps for inserting the i-th element, so the average time complexity of binary insertion sort is ?(N^2).
Binary insertion sort is an in-place sorting algorithm. This means that it only requires a constant amount of additional space. We sort the given array by shifting and inserting the elements.
Therefore, the space complexity of this algorithm is O(1) if we use iterative binary search. It will be O(logN) if we use recursive binary search because of O(log N) recursive calls.
Binary insertion sort works efficiently for smaller arrays (<= 25 elements). This algorithm also works well for almost-sorted arrays, where the elements are near their position in the sorted array.
However, when the size of the array is large, the binary insertion sort doesn’t perform well. We can use other sorting algorithms like merge sort or quicksort in such cases.
Making fewer comparisons is also one of the strengths of this sorting algorithm; therefore, it is efficient to use it when the cost of comparison is high.
As stated earlier, binary insertion sort is an improvement of insertion sort. We reduce the number of comparisons in insertion sort by using binary search instead of linear search.
Note: Both the algorithms are in place and use O(1) space complexity. However, if we use recursive binary search in binary insertion sort, its space complexity will become O(log N) due to O(log N) recursive calls.
Question 1. Is Binary insertion sort a stable sorting algorithm?
Answer: Yes, binary insertion sort is a stable sorting algorithm. This means that two different elements with the same value will appear in the same order in the final sorted array as they appeared in the initial array.
In each iteration, we find the element’s position just greater than our current element in the sorted subarray and insert it there. Thus, if there were any other elements with the same value before our current element in the initial array, they will be present before it in the final sorted array.
Question 2. Which sorting algorithm between binary insertion sort and bubble sort uses fewer swaps?
Answer: Both binary insertion sort and bubble sort use the same number of swaps. For an element at index “i†in the initial array, if its position in the sorted array is “j,†both the algorithms will take abs(i-j) swaps to place it in its sorted position. The total number of swaps used in both the algorithms is equal to the inversion count of the array.
Question 3. How many maximum comparisons will be made in binary insertion sort in one iteration?
Answer: O(Log N). This will happen when we are in the n-th iteration, and the position where the current element should be inserted is such that the binary search takes O(log N) steps.
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 their dream jobs at Google, Facebook, Apple, Netflix, Amazon, and other Tier-1 tech companies.
———-
Article contributed by Problem Setters Official
Time Zone:
Get your enrollment process started by registering for a Pre-enrollment Webinar with one of our Founders.
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
Just drop your name and email so we can send your Power Patterns PDF straight to your inbox. No Spam!
By sharing your contact details, you agree to our privacy policy.
Time Zone: Asia/Dhaka
We’ve sent the Power Patterns PDF to your inbox — it should arrive in the next 30 seconds.
📩 Can’t find it? Check your promotions or spam folder — and mark us as safe so you don’t miss future insights.
We’re hosting a private session where FAANG insiders walk through how they actually use these Power Patterns to crack interviews — and what sets top performers apart.
🎯 If you liked the PDF, you’ll love what we’re sharing next.
Time Zone:
