Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Binary Insertion Sort?
3.
Binary Insertion Sort Application
4.
How Does Binary Insertion Sort Work?
5.
Example of Binary Insertion Sort
6.
Binary Insertion Sort Algorithm
7.
Implementation of Binary Insertion Sort
7.1.
C
7.2.
C++
7.3.
Java
7.4.
Python
7.5.
Javascript
7.6.
C#
7.7.
Binary Insertion Sort Complexities
7.7.1.
Time Complexity of Binary Insertion Sort
7.7.2.
Space complexity of Binary Insertion Sort
8.
Frequently Asked Questions
8.1.
What is the difference between straight and binary insertion sort?
8.2.
What is binary search in sorting?
8.3.
Can binary search be used for insertion sort?
8.4.
Is binary search faster than insertion sort?
8.5.
When the time complexities of Binary Insertion Sort and Insertion Sort are similar. What is the use of Binary Insertion Sort then?
9.
Conclusion
Last Updated: May 3, 2024
Easy

Binary Insertion Sort

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

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.

Binary Insertion Sort

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

  1. Initialization: The algorithm starts by considering the first element of the array as the sorted sequence.
  2. Iterative Sorting: For each subsequent element in the array, Binary Insertion Sort performs the following steps:
    1. Use binary search to find the correct position in the sorted sequence where the current element should be inserted.
    2. Shift elements to the right to make space for the new element to be inserted at the correct position.
    3. Insert the current element into its correct position in the sorted sequence.
  3. Repeat: Continue this process for each remaining element in the array until the entire array is sorted.

Example of Binary Insertion Sort

Input: Array: 

input

Output:

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.

example

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

example

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

example

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

sorted array as output

Binary Insertion Sort Algorithm

  1. We will start by iterating the element from the second element to the last element.
  2. Then, we will store the currently considered element in a key.
  3. 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.
  4. So, we will shift all the elements from the index position to [i-1] towards the right.
  5. 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;

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

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

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

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

void insertionSortfxn(int arr[], int num) {
int i, j, k, select, position;

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

while (j >= position) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = select;
}
}

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

insertionSortfxn(array, size);

printf("The Sorted Array is:");
for (i = 0; i < size; i++)
printf(" %d", array[i]);

return 0;
}

C++

#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;
}

Java

import java.util.*;

class Main {
static 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)
return (element > arr[l]) ? (l + 1) : l;

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

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

static void insertionSortfxn(int arr[], int num) {
int i, j, k, select, position;

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

while (j >= position) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = select;
}
}

public static void main(String[] args) {
int array[] = {9, 7, 2, 6, 4};
int size = array.length, i;

insertionSortfxn(array, size);

System.out.print("The Sorted Array is:");
for (i = 0; i < size; i++)
System.out.print(" " + array[i]);

System.out.println();
}
}

Python

def binary_search(arr, element, l, h):
m = (l + h) // 2

if element == arr[m]:
return m + 1

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

if element > arr[m]:
return binary_search(arr, element, m + 1, h)

return binary_search(arr, element, l, m - 1)


def insertion_sort(arr):
for i in range(1, len(arr)):
j = i - 1
select = arr[i]
position = binary_search(arr, select, 0, j)

while j >= position:
arr[j + 1] = arr[j]
j -= 1

arr[j + 1] = select


array = [9, 7, 2, 6, 4]
insertion_sort(array)

print("The Sorted Array is:", end="")
for num in array:
print(" " + str(num), end="")
print()

Javascript

function binarySearch(arr, element, l, h) {
let m = Math.floor((l + h) / 2);

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

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

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);

while (j >= position) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = select;
}
}

let array = [9, 7, 2, 6, 4];
insertionSort(array);

process.stdout.write("The Sorted Array is:");
array.forEach(num => process.stdout.write(" " + num));
console.log();

C#

using System;

class Program
{
static int BinarySearch(int[] arr, int element, int l, int h)
{
int m = (l + h) / 2;

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

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

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);

while (j >= position)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = select;
}
}

static void Main(string[] args)
{
int[] array = { 9, 7, 2, 6, 4 };
int size = array.Length;

InsertionSort(array, size);

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

Output:

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(N2). 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.

Read More - Time Complexity of Sorting Algorithms

Refer to know about :  Topological sort

Frequently Asked Questions

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.

We hope that this blog has helped you enhance your knowledge about Binary Insertion Sort and if you like to learn more, check out our articles Insertion Sort for singly linked listsQuickSort on Doubly Linked ListSorted insertion in a Sorted Linked ListMergeSort on Doubly Linked ListBubbleSort on Doubly Linked List, and Quicksort on Singly Linked List

 

Recommended problems -


Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, and many more! If you wish to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Counting Sort
Next article
Selection Sort in C, C++, Java, Python & C#
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass