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;

}

}

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);

}

}