Welcome to our in-depth exploration of the Binary Insertion Sort algorithm! Sorting is a fundamental operation in computer science, and Binary Insertion Sort offers a refined approach to this task. In this blog, we'll delve into why sorting algorithms are essential in programming and why Binary Insertion Sort stands out among them.

Now, let’s get started with our article.

What is Binary Insertion Sort?

Binary insertion sort is simply an insertion sort. It is just implemented using binary search instead of linear search. Changing the type of search improves the time complexity of the sorting algorithm. It is because the comparison we do is reduced for one element from O(n) to O(logn).

It will work faster when the array is already sorted. Thus, making it an adaptive algorithm. It is also a stable sorting algorithm, that means the elements with the same values appear in the same order for both the final array as well as the initial array.

Binary Insertion Sort Application

When we are provided with an array of elements. We generally prefer to do merge sort or quick sort. It is quite beneficial when the number of elements is large. But for the cases when the numbers of elements are less, we must do a binary insertion sort. The binary Insertion Sort can be most efficiently used when the number of elements are less.

How Does Binary Insertion Sort Work?

inary Insertion Sort is an optimized variant of the traditional insertion sort algorithm. While the insertion sort algorithm iterates through each element of the array to find its correct position in the sorted sequence, Binary Insertion Sort takes advantage of binary search to efficiently locate this position.

Here's how Binary Insertion Sort works:

Initialization: The algorithm starts by considering the first element of the array as the sorted sequence.

Iterative Sorting: For each subsequent element in the array, Binary Insertion Sort performs the following steps:

Use binary search to find the correct position in the sorted sequence where the current element should be inserted.

Shift elements to the right to make space for the new element to be inserted at the correct position.

Insert the current element into its correct position in the sorted sequence.

Repeat: Continue this process for each remaining element in the array until the entire array is sorted.

Example of Binary Insertion Sort

Input: Array:

Output:

Explanation:

👉We will start by assuming that the first element is already sorted. We will now take the second element and store it as a variable. Afterwards, we will use binary search to find the element on the left of the current element. In this particular case, we have only one element on the left side i.e., 9, which is greater than 7. So, we shift 9 one index towards the right and place 7 at its position.

👉Now, we will take the third element, i.e. 2. The elements which are before the current element are sorted till now. We will store 2 in the key and find the element just greater than 2 in the sorted part using binary search. Here, the required elements will be 7. So, we will now shift 7 and 9 one index towards the right and place 2 at the position of 7 before shifting.

👉We will now take the 4th element, i.e. 6, and store it in the key. Now using binary search, we will find the element just greater than 6 in the sorted part. In this case, the required elements will be 7. Now we will again shift 7 and 9 one index towards the right and place 6 at the position of 7 before shifting.

👉We now take the last element, which is 4. Now we will find the element just greater than it in the sorted part. The required element is now 6. We shift 6, 7, and 9 one index towards the right and we will place 4 at the position of 6. Hence, the array is sorted.

Binary Insertion Sort Algorithm

We will start by iterating the element from the second element to the last element.

Then, we will store the currently considered element in a key.

Now, find the position of the elements which are just greater than A[i] elements. We will search for these elements in the subarray from A[0] to A[i-1] using binary search. Let’s say this element is at the index position.

So, we will shift all the elements from the index position to [i-1] towards the right.

In the end, A[index position] element value will be stored in the key. And it will then get interchanged.

Implementation of Binary Insertion Sort

C

C++

Java

Python

Javascript

C#

C

#include <stdio.h>

int binarySearchfxn(int arr[], int element, int l, int h) { int m = (l + h) / 2;

#include <bits/stdc++.h> using namespace std; #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);

//---------------------------Function for binary search---------------------------// int binarySearchfxn(int arr[], int element, int l, int h) { int m = (l + h) / 2;

if (element == arr[m]) return m + 1;

if (h <= l) if (element > arr[l]) return (l + 1); else return l;

if (element > arr[m]) return binarySearchfxn(arr, element, m + 1, h);

return binarySearchfxn(arr, element, l, m - 1); }

//---------------------------Function for insertion sort---------------------------// void insertionSortfxn(int arr[], int num) { int i, j, k, select, position;

for (i = 1; i < num; ++i) { j = i - 1; select = arr[i];

// finding a location where elements should be inserted position = binarySearchfxn(arr, select, 0, j);

// Moving elements from the positions while (j >= position) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = select; } }

//---------------------------Main Function---------------------------// int main() { FAST; int array[] = { 9,7,2,6,4 }; int size = sizeof(array) / sizeof(array[0]), i;

insertionSortfxn(array, size);

cout <<"The Sorted Array is:"; for (i = 0; i < size; i++) cout <<" "<< array[i];

return 0; }

You can also try this code with Online C++ Compiler

if (element > arr[m]) return binarySearch(arr, element, m + 1, h);

return binarySearch(arr, element, l, m - 1); }

function insertionSort(arr) { for (let i = 1; i < arr.length; ++i) { let j = i - 1; let select = arr[i]; let position = binarySearch(arr, select, 0, j);

if (element > arr[m]) return BinarySearch(arr, element, m + 1, h);

return BinarySearch(arr, element, l, m - 1); }

static void InsertionSort(int[] arr, int num) { for (int i = 1; i < num; ++i) { int j = i - 1; int select = arr[i]; int position = BinarySearch(arr, select, 0, j);

Console.Write("The Sorted Array is:"); foreach (int num in array) Console.Write(" " + num); Console.WriteLine(); } }

Output:

Binary Insertion Sort Complexities

Time Complexity of Binary Insertion Sort

⭐The time complexity of binary insertion sort in the average and worst case is O(N^{2}). While for the best case, the time complexity will be O(NlogN). It is because the num of comparisons for inserting one element is O(log N), and for N elements, it will be O(NlogN).

Space complexity of Binary Insertion Sort

⭐The space complexity of the Binary Insertion Sort algorithm is O(1). As it is an in-place sorting algorithm, the space complexity is constant.

What is the difference between straight and binary insertion sort?

Straight insertion sort iterates linearly to find the correct position for each element, while binary insertion sort uses binary search for efficient position finding.

What is binary search in sorting?

Binary search is a search algorithm used to find the position of a target value within a sorted array by repeatedly dividing the search interval in half.

Can binary search be used for insertion sort?

Yes, binary search can be used for insertion sort to efficiently find the correct position for each element in the sorted sequence.

Is binary search faster than insertion sort?

Binary search is not inherently faster than insertion sort. While binary search is efficient for finding positions, insertion sort's overall time complexity may vary depending on the input data.

When the time complexities of Binary Insertion Sort and Insertion Sort are similar. What is the use of Binary Insertion Sort then?

Binary insertion sort is preferred because it is implemented using binary search instead of linear search. The comparison we do is reduced for one element from O(n) to O(logn). The time complexity improves.

Conclusion

This article briefly discussed what is binary insertion sort. We also discussed the applications, examples, algorithm, and implementation of Binary Insertion Sort.