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.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#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: \n");     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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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.