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?
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.
Applications of Binary Insertion Sort
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.
Binary Insertion Sort Example
Suppose we need to sort the following array:
We assume that the first element is already sorted.
We take the second element and store it in a variable (key).
Now, we use binary search to find the element on the left of the current element, which is just greater than it.
In this case, we have only one element, 8, and it is greater than 6. So, we shift 8 one index towards the right and place 6 at its position.
The array now looks like this:
Now, we take the third element, 1. Note that all the elements before the current element are sorted.
We store 1 in key and find the element just greater than 1 in the sorted part using binary search.
Here, the required element is 6. So, we shift 6 and 8 one index towards the right and place 1 at the position of 6 before shifting.
The array now looks like this:
We now take the 4th element, 5, and store it in key.
Using binary search, we find the element just greater than 5 in the sorted part. In this case, the required element is 6.
Again, we shift 6 and 8 one index towards the right and place 5 at the position of 6 before shifting.
The array now looks like this:
We now take the last (5th) element, which is 3, and find the element just greater than it in the sorted part.
The required element is 5. We shift 5, 6, and 8 one index towards the right and place 3 at the position of 5 before shifting.
The resulting array is:
We have sorted the given array using binary insertion sort.
Binary Insertion Sort Algorithm
Binary insertion sort for array A:
Step 1: Iterate the array from the second element to the last element.
Step 2: Store the current element A[i] in a variable key.
Step 3: Find the position of the element just greater than A[i] in the subarray from A[0] to A[i-1] using binary search. Say this element is at index pos.
Step 4: Shift all the elements from index pos to i-1 towards the right.
procedure binarySearch(Array, N, key)
L = 0
R = N
while L < R:
mid = (L + R)/2
if Array[mid] <= key:
L = mid + 1
else:
R = mid
return L
end procedure
procedure binaryInsertionSort(Array)
for i = 1 to length(Array) do:
key = Array[i]
pos = binarySearch(Array, key, 0, i-1)
j = i
while j > pos
Array[j] = Array[j-1]
j = j-1
Array[pos] = key
end for
end procedure
# This function will return the index of element
# just greater than 'key' in Array from 0-N
def binarySearch(Array, N, key):
L = 0
R = N
while(L < R):
mid = (L + R)//2
if (Array[mid] <= key):
L = mid + 1
else:
R = mid
return L
def binaryInsertionSort(Array):
# We assume the 1st element of Array to be already sorted.
# Now we start iterating from the 2nd element to the last element.
for i in range (1,len(Array)):
key = Array[i]
pos = binarySearch(Array, i, key)
# 'pos' will now contain the index where 'key' should be inserted.
j = i
# Shifting every element from 'pos' to 'i' towards right.
while(j > pos):
Array[j] = Array[j-1]
j = j-1
# Inserting 'key' in its correct position.
Array[pos] = key
print("The array after",i,"iterations =", *Array)
Array = [8, 6, 1, 5, 3]
binaryInsertionSort(Array)
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.
Best Case
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.
Average Case
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).
Space Complexity Analysis
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.
Strengths and Weaknesses of Binary Insertion Sort
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.
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.
FAQs on Binary Insertion Sort
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.
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.
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.
.png)
