Repository: TheAlgorithms/Java
Pull request #3206 (2022-08-03 17:54:23)

Create a new Binary Insertion Sort Algorithm
### **Describe your change:**

- [x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References
[Binary Insertion Sort](https://www.geeksforgeeks.org/binary-insertion-sort/)

### **Checklist:**


- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation..



Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/BinaryInsertionSort.java b/src/main/java/com/thealgorithms/sorts/BinaryInsertionSort.java
new file mode 100644
index 00000000..1a2b1159
--- /dev/null
+++ b/src/main/java/com/thealgorithms/sorts/BinaryInsertionSort.java
@@ -0,0 +1,32 @@
+package com.thealgorithms.sorts;
+public class BinaryInsertionSort{
+   
+
+ 
+    // Binary Insertion Sort method   
+    public int[] binaryInsertSort(int[] array){
+       
+        for(int i = 1; i < array.length; i++){
+           
+        	int temp=array[i];
+            int low = 0;            
+            int high = i - 1;  
+           
+            while(low <= high){                
+                int mid = (low + high) / 2;                
+                if(temp < array[mid]){                    
+                    high = mid - 1;                
+                }else{                    
+                    low = mid + 1;
+                }       
+            }
+           
+            for(int j = i; j >= low + 1; j--){            
+                array[j] = array[j - 1];                                                      
+            }       
+           
+            array[low] = temp;       
+        }   
+        return array;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/BinaryInsertionSortTest.java b/src/test/java/com/thealgorithms/sorts/BinaryInsertionSortTest.java
new file mode 100644
index 00000000..70d0abad
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/BinaryInsertionSortTest.java
@@ -0,0 +1,26 @@
+package com.thealgorithms.sorts;
+import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.*;
+
+
+
+class BinaryInsertionSortTest {
+	BinaryInsertionSort BIS= new BinaryInsertionSort();
+	
+    @Test
+    // valid test case
+    public void BinaryInsertionSortTestNonDuplicate() {
+    	int[] array = {1,0,2,5,3,4,9,8,10,6,7};	
+    	int [] expResult= {0,1,2,3,4,5,6,7,8,9,10};
+        int[] actResult = BIS.binaryInsertSort(array);
+        assertArrayEquals(expResult,actResult);
+    }
+
+    @Test
+    public void BinaryInsertionSortTestDuplicate() {
+    	int[] array = {1,1,1,5,9,8,7,2,6};	
+    	int [] expResult= {1,1,1,2,5,6,7,8,9};
+        int[] actResult = BIS.binaryInsertSort(array);
+        assertArrayEquals(expResult,actResult);
+    }
+}