Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Binary Insertion Sort

Last updated by Swaminathan Iyer on Sep 25, 2024 at 10:58 PM | Reading time: 11 minutes

The fast well prepared banner

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Binary Insertion Sort
Hosted By
Ryan Valles
Founder, Interview Kickstart
strategy
Our tried & tested strategy for cracking interviews
prepare list
How FAANG hiring process works
hiring process
The 4 areas you must prepare for
hiring managers
How you can accelerate your learnings

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:

What Is Insertion Sort?

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.”

What Is Binary Insertion Sort?

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.

How Does Binary Insertion Sort Work?

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:

Binary Insertion Sort Example
  1. We assume that the first element is already sorted.
  2. We take the second element and store it in a variable (key).
  3. Now, we use binary search to find the element on the left of the current element, which is just greater than it.
  4. 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:

Binary Sort Java
  1. Now, we take the third element, 1. Note that all the elements before the current element are sorted.
  2. We store 1 in key and find the element just greater than 1 in the sorted part using binary search.
  3. 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:

  1. We now take the 4th element, 5, and store it in key.
  2. Using binary search, we find the element just greater than 5 in the sorted part. In this case, the required element is 6.
  3. 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:

  1. We now take the last (5th) element, which is 3, and find the element just greater than it in the sorted part.
  2. 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.
  • Step 5: A[pos] = key.

Binary Insertion Sort Pseudocode

Binary Insertion Sort Code

Output

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

Binary Insertion Sort Complexities

Time Complexity Analysis

Worst Case

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.

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.

Insertion Sort vs. Binary Insertion Sort

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.

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.

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 their dream jobs at Google, Facebook, Apple, Netflix, Amazon, and other Tier-1 tech companies.

Sign up now!

----------

Article contributed by Problem Setters Official

Last updated on: 
September 25, 2024
Author

Swaminathan Iyer

Product @ Interview Kickstart | Ex Media.net | Business Management - XLRI Jamshedpur. Loves building things and burning pizzas!

Attend our Free Webinar on How to Nail Your Next Technical Interview

Register for our webinar

How to Nail your next Technical Interview

1
Enter details
2
Select webinar slot
First Name Required*
Last Name Required*
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

Binary Insertion Sort

Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Our tried & tested strategy for cracking interviews
blue tick
How FAANG hiring process works
blue tick
The 4 areas you must prepare for
blue tick
How you can accelerate your learnings
Register for Webinar
entroll-image