Binary insertion sort

#1

please explain me the code for binary insertion sort

#2

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.
I have written the code and added comments to make it easy to understand. Let me know if you have any further queries.

#3

please explain return -(lo+1);
in your code
thank you for your reply

#4

The binary search function returns the index of the searched key, if it is found in the array; otherwise, (-(insertion point) – 1). The insertion point is the point at which the key would be inserted into the array: the index of the first element greater than the key. We return negative number to represent that the key was not found in the array.

You would be able to understand this more clearly if you take an example and do a dry run on paper.

#5

the key can’t be found because we need to insert the element from unsorted part to sorted part
why (-(insertion point)-1) i think you mistaken it.

#6

int j = Math.abs(binarySearch(arr, 0, i-1, temp) + 1);
please help me with this line also
why math.abs?

#7

I know the key won’t be found, I have written the generalized code for binary search. In this case, it will always return (-(insertion point)-1). If you dry run, you will see that (insertion point -1) will always be the point at which the key would be inserted into the array: the index of the first element greater than the key. And we need to find that point only for our binary insertion sort algorithm.

I have used math.abs here because the binary search function will return a negative value and index cannot be negative.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.