# Binary Insertion Sort

We can use binary search to reduce the number of comparisons in normal insertion sort. Binary Insertion Sort uses binary search to find the proper location to insert the selected item at each iteration.
In normal insertion sort, it takes O(n) comparisons(at nth iteration) in worst case. We can reduce it to O(log n) by using binary search.

## C/C++

 `// C program for implementation of binary insertion sort ` `#include ` ` `  `// A binary search based function to find the position ` `// where item should be inserted in a[low..high] ` `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[] = {37, 23, 0, 17, 12, 72, 31, ` `              ``46, 100, 88, 54}; ` `    ``int` `n = ``sizeof``(a)/``sizeof``(a), i; ` ` `  `    ``insertionSort(a, n); ` ` `  `    ``printf``(````"Sorted array: "````); ` `    ``for` `(i = 0; i < n; i++) ` `        ``printf``(``"%d "``,a[i]); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java Program implementing ` `// binary insertion sort ` ` `  `import` `java.util.Arrays; ` `class` `GFG ` `{ ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``final` `int``[] arr = {``37``, ``23``, ``0``, ``17``, ``12``, ``72``, ``31``, ` `                             ``46``, ``100``, ``88``, ``54` `}; ` ` `  `        ``new` `GFG().sort(arr); ` ` `  `        ``for``(``int` `i=``0``; i

## Python

 `# Python Program implementation   ` `# of binary insertion sort ` ` `  `def` `binary_search(arr, val, start, end): ` `    ``# we need to distinugish whether we should insert ` `    ``# before or after the left boundary. ` `    ``# imagine  is the last step of the binary search ` `    ``# and we need to decide where to insert -1 ` `    ``if` `start ``=``=` `end: ` `        ``if` `arr[start] > val: ` `            ``return` `start ` `        ``else``: ` `            ``return` `start``+``1` ` `  `    ``# this occurs if we are moving beyond left's boundary ` `    ``# meaning the left boundary is the least position to ` `    ``# find a number greater than val ` `    ``if` `start > end: ` `        ``return` `start ` ` `  `    ``mid ``=` `(start``+``end)``/``2` `    ``if` `arr[mid] < val: ` `        ``return` `binary_search(arr, val, mid``+``1``, end) ` `    ``elif` `arr[mid] > val: ` `        ``return` `binary_search(arr, val, start, mid``-``1``) ` `    ``else``: ` `        ``return` `mid ` ` `  `def` `insertion_sort(arr): ` `    ``for` `i ``in` `xrange``(``1``, ``len``(arr)): ` `        ``val ``=` `arr[i] ` `        ``j ``=` `binary_search(arr, val, ``0``, i``-``1``) ` `        ``arr ``=` `arr[:j] ``+` `[val] ``+` `arr[j:i] ``+` `arr[i``+``1``:] ` `    ``return` `arr ` ` `  `print``(``"Sorted array:"``) ` `print` `insertion_sort([``37``, ``23``, ``0``, ``17``, ``12``, ``72``, ``31``, ` `                        ``46``, ``100``, ``88``, ``54``]) ` ` `  `# Code contributed by Mohit Gupta_OMG  `

## C#

 `// C# Program implementing ` `// binary insertion sort ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = {37, 23, 0, 17, 12, 72, 31, ` `                             ``46, 100, 88, 54 }; ` ` `  `        ``sort(arr); ` ` `  `        ``for``(``int` `i = 0; i < arr.Length; i++) ` `            ``Console.Write(arr[i] + ``" "``); ` `    ``} ` ` `  `    ``public` `static` `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(Array.BinarySearch( ` `                              ``array, 0, i, x) + 1); ` ` `  `            ``// Shifting array to one location right ` `            ``System.Array.Copy(array, j, array, ` `                                         ``j+1, i-j); ` ` `  `            ``// Placing element at its correct ` `            ``// location ` `            ``array[j] = x; ` `        ``} ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

## PHP

 ` ``\$a``[``\$low``]) ?  ` `                       ``(``\$low` `+ 1) : ``\$low``;  ` ` `  `    ``\$mid` `= (int)((``\$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'  ` `function` `insertionSort(&``\$a``, ``\$n``)  ` `{  ` `    ``\$i``; ``\$loc``; ``\$j``; ``\$k``; ``\$selected``;  ` ` `  `    ``for` `(``\$i` `= 1; ``\$i` `< ``\$n``; ++``\$i``)  ` `    ``{  ` `        ``\$j` `= ``\$i` `- 1;  ` `        ``\$selected` `= ``\$a``[``\$i``];  ` ` `  `        ``// find location where selected  ` `        ``// item should be inserted  ` `        ``\$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 Code ` `\$a` `= ``array``(37, 23, 0, 17, 12, 72,  ` `           ``31, 46, 100, 88, 54);  ` `            `  `\$n` `= sizeof(``\$a``);  ` ` `  `insertionSort(``\$a``, ``\$n``);  ` ` `  `echo` ```"Sorted array: "````;  ` `for` `(``\$i` `= 0; ``\$i` `< ``\$n``; ``\$i``++)  ` `    ``echo` `"\$a[\$i] "``;  ` ` `  `// This code is contributed by  ` `// Adesh Singh ` `?> `

/div>

Output:

```Sorted array:
0 12 17 23 31 37 46 54 72 88 100```

Time Complexity: The algorithm as a whole still has a running worst case running time of O(n2) because of the series of swaps required for each insertion.