# 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 ith 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(n2) 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 `   `// 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), 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.
 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.