# Binary Insertion Sort – Explanation and Implementation

Binary Insertion sortis 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 2 ) 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: /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. 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.