Binary Insertion Sort is a modified version of insertion sort.Â
In insertion sort, we are using linear search to place an item in its correct position, but binary insertion sort uses binary search to do the same.
Number of sorted inputs array = 8
The binary search uses the middle index item.
Index 8/2 = 4Â Â Â Â Â Â (1st comparison)
Index 4/2 = 2Â Â Â Â Â Â (2nd Comparison)
Index 2/2 = 1Â Â Â Â Â Â (3rd Comparison)
In the linear search of insertion sort, we have the number of comparisons = n. But in binary search of binary insertion sort, we reduce the number of comparisons = log n.
Time Complexity of Insertion sort and Binary insertion sort
| Insertion Sort | Binary Insertion Sort | |
|---|---|---|
Best Case | O(n) | O(n) |
Average Case | O(n^2) | O(nlogn) |
Worst Case | O(n^2) | O(nlogn) |
Unsorted input array is Y[i], i= 1
Sorted output array is X[j], j = 0
- Y[1] = X[j+1]
- for Y[2] to Y[n] execute statement 3-5
- Compare and insert Y[i] into sorted output array X[1…j] from right.
- Binary Search starts, choose a number X[j], equal or less than Y[i].
Right shift all the values from X[j+1] to end of sorted output array and Place Y[i] = X[j+1].
Â
Program of binary insertion sort in C
Â
Â
Advantage of binary insertion sort
- Reduces time complexity.
Disadvantage of binary insertion sort
- We cannot use this sort in our manual work. Insertion sort we can do.
- Somewhat Complex.
Test Yourself
Q1- What is Binary Insertion Sort, and how does it differ from regular Insertion Sort?
Binary Insertion Sort is a variation of the traditional Insertion Sort algorithm that uses binary search to find the correct position for inserting an element into the sorted part of the array. While regular Insertion Sort performs a linear search to find the proper position, Binary Insertion Sort takes advantage of the logarithmic time complexity of binary search, making it more efficient for larger datasets.
Q2- How does Binary Insertion Sort work, step-by-step?
The Binary Insertion Sort starts by assuming the first element as the sorted part. Then, it iterates through the unsorted part of the array, using binary search to find the correct position for each element in the sorted part. The element is then inserted at that position, and the process continues until all elements are sorted.
Q3- How does the choice of data structure impact the performance of Binary Insertion Sort?
The choice of data structure can influence the performance of Binary Insertion Sort. When implementing binary search for finding the correct position, using an array-based data structure allows for faster access to elements, resulting in better performance compared to using linked lists.
Q4- What are some possible modifications to improve the performance of Binary Insertion Sort?
Binary Insertion Sort with Binary Trees
Instead of using a simple array, you can implement Binary Insertion Sort using a binary search tree or a balanced binary tree like AVL tree or Red-Black tree. This can further reduce the time complexity of searching for the correct position.
Parallelization
If you have access to multiple processors or cores, you can parallelize the Binary Insertion Sort algorithm to take advantage of concurrent processing, thereby speeding up the sorting process for large arrays.
Q5- Are there any specific scenarios where Binary Insertion Sort is not recommended?
Binary Insertion Sort is not recommended for sorting large datasets, especially when a more efficient sorting algorithm like Merge Sort or Heap Sort is available. Additionally, if the dataset is randomly shuffled or has a high number of inversions, Binary Insertion Sort may not be the best choice due to its quadratic time complexity.
Q6- Which part of Binary Insertion Sort takes advantage of the logarithmic time complexity?
It efficiently finds the correct position for each element in the sorted part of the array.
Q7- What is the main benefit of using Binary Insertion Sort over regular Insertion Sort?
The main benefit of using Binary Insertion Sort is the reduction in the number of comparisons required to find the correct position for each element. This results in improved efficiency for larger datasets.
Q8- Is Binary Insertion Sort a stable sorting algorithm?
Yes, Binary Insertion Sort is a stable sorting algorithm. It maintains the relative order of equal elements during the sorting process.
Q9- What type of time complexity does Binary Insertion Sort exhibit when sorting small datasets?
For small datasets, Binary Insertion Sort can demonstrate relatively good performance, close to linear time complexity, due to its O(n) best-case scenario.
