Binary Insertion Sort – Explanation and Implementation

Binary Insertion sort is a variant of Insertion sorting in which proper location to insert the selected element is found using the binary search.

Read Insertion Sort in detail for complete understanding.

Binary search reduces the number of comparisons in order to find the correct location in the sorted part of data.

In worst case scenario – Normal insertion sort takes O( i ) time in its i^th iteration whereas using binary search can reduce it to O(log( i )).

Note – Overall time complexity of the algorithm in the worst case is still O(n²) because of the number of swaps required to put every element at the correct location.

Implementation of Binary Insertion Sort in C

#include <stdio.h>

// A binary search based function to find the position
// where item should be inserted
int binarySearch(int a[], int item, int low, int high)
{
	if (high <= low)
		return (item > a[low])? (low + 1): low;

	int mid = (low + high)/2;

	if(item == a[mid])
		return mid+1;

	if(item > a[mid])
		return binarySearch(a, item, mid+1, high);
	return binarySearch(a, item, low, mid-1);
}

// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
	int i, loc, j, k, selected;

	for (i = 1; i < n; ++i)
	{
		j = i - 1;
		selected = a[i];

		// find location where selected sould be inseretd
		loc = binarySearch(a, selected, 0, j);

		// Move all elements after location to create space
		while (j >= loc)
		{
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = selected;
	}
}

// Driver program to test above function
int main()
{
	int a[] = {4, 10, 3, 1, 9, 15};
	int n = sizeof(a)/sizeof(a[0]), i;

	insertionSort(a, n);

	printf("Sorted array: 
");
	for (i = 0; i < n; i++)
		printf("%d ",a[i]);

	return 0;
}

Output:-

Sorted array - 1 3 4 9 10 15

Implementation of Binary Insertion Sort in Java

In this implementation, I have used library functions for binary search and shifting array to one location right. To understand in detail on how binary search works read this article.

package com.codingeek.algorithms.sorting;

import java.util.Arrays;

class BinaryInsertionSort{

    public static void main(String[] args) {
    	final int[] input = { 4, 10, 3, 1, 9, 15 };
        System.out.println("Before Sorting - " + Arrays.toString(input));
        new BinaryInsertionSort().sort(input);
        System.out.println("After Sorting - " + Arrays.toString(input));
    }
	
    public void sort(int array[]) {
        for (int i = 1; i < array.length; i++) {
        	   int x = array[i];
        	   
        	   // Find location to insert using binary search
        	   int j = Math.abs(Arrays.binarySearch(array, 0, i, x) + 1);
        	   
        	   //Shifting array to one location right
        	   System.arraycopy(array, j, array, j+1, i-j);
        	   
        	   //Placing element at its correct location
        	   array[j] = x;
        }
}

Output:-
Before Sorting - [4, 10, 3, 1, 9, 15]
After Sorting - [1, 3, 4, 9, 10, 15]

Do share the wisdom and share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.

Keep Learning.. Happy Learning.. 🙂

Recommended -