Binary Insertion Sort

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: 

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

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

You can also try this code with Online C Compiler

Run Code

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

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

Run Code

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

You can also try this code with Online Java Compiler

Run Code

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

You can also try this code with Online Python Compiler

Run Code

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

You can also try this code with Online Javascript Compiler

Run Code

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:

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²). 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 lists, QuickSort on Doubly Linked List, Sorted insertion in a Sorted Linked List, MergeSort on Doubly Linked List, BubbleSort on Doubly Linked List, and Quicksort on Singly Linked List. 

Recommended problems -

• Leaf Nodes in Binary Tree
• Vertical Order Traversal of a Binary Tree
• Binary Array Sorting
• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, 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 problems, interview 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!