Binary Insertion sort - Getting speed

"Please lord, let me prove that winning in the casino won't spoil me." - Bubbly

After we helped Bubbly arrange her cards, she was rocking in the casino. She is now a winning sensation in the Venetian. But as her game has improved, so has her need to be faster and smarter with her cards.

So far as I remember, we had used the fastest way we knew to get her cards sorted. But now with her improved game and competition, that seems slower and we need to find even faster ways to get her cards in order.

Is there a way we can achieve this? Lets try to find out by carefully examining how the Insertion sort works.

As you must have noticed in the post Bubbly goes to Las Vegas, insertion sort works by taking one element at a time, searching its sorted position in already sorted partial array and putting it there. To search this position, we iterated over all the elements in the partially sorted portion linearly and compared the element at hand with each element until we got the desired sorted position for this element.

Let me highlight a few keywords in the above statement : insertion sort works by taking one element at a time, searching its sorted position in already sorted partial array  and putting it there.

If you are following this blog, which I wish you were but I am sure you are not,  you would remember from the post You are searching so hard..., that our study for sorting started because searching in a sorted array is faster.

As can be seen, the insertion sort as of now searches for the element position by simple iteration and comparison which does not take into consideration the fact that we know the arrangement of numbers in the already sorted array. This type of search is called a linear search. This is fine for a small array. But for a larger array this can turn out to be slower as irrespective of the position of the to be searched element in the array, we will iterate through all the elements until we find the one we are seeking. So what is it that we can do so that this search will happen faster?

Binary search for rescue:

I am quite sure, most of you already know Binary search as well. Have you ever played the game "Guess the number", where you ask your friend to pick up a random number and tell them that you will  guess it? Those who answered yes instantly already know the Binary search algorithm. And for others, A quick refresher.

Lets assume that Bubbly and her friend Silly are playing this game.

Bubbly: Hey Silly, wanna play a game?

     Silly: Of course, I am game for a game. Always!

Bubbly: Ok Its a game of numbers.

     Silly: Maths?? :( No way.

Bubbly: Don' worry, you don't have to do any math. You Just have to pick a number between 1 to 10 and I will tell you what number you picked.

     Silly: That sounds fun.

Bubbly: I will guess the number but if its incorrect, I will ask you some hint questions and I would expect you to be honest with me.

     Silly: Fair enough!

Bubbly: Ok so lets get started. Pick a number between 1 to 10 and don't tell me the number. :)

     Silly: umm.. (7)...ok I did.

Bubbly: OK. Let me guess!!.. ummm Is it 5?

     Silly: Nope :).

Bubbly: Okay, is it less than 5 or greater than 5?

     Silly: Greater. As if she is ever gonna be able to tell me what I picked. HAHAHAHA

Bubbly: Okay! Is it 8?

     Silly: Nope, no no.

Bubbly: Okay, is it less than 8 or greater than 8?

     Silly: Less. Oh man, how is she closing in on the number?

Bubbly: Okay, is it 6?

     Silly: Nope. You are never going to find it.

Bubbly: Great! Actually I have found it. It is 7.

     Silly: No Way? How did you guess?

Bubbly: La lala lalalalalala....

Okay, So as you can see, that was fast.

What Bubbly did was the efficient use of Binary search algorithm.

Here's a snapshot of what was going on in Bubbly's head:

Instead of looking through each element of an array linearly, binary search leverages the knowledge that the array is sorted and looks for the desired item by comparing it with the element at the middle of the array. If the element matches, all good, otherwise, we can simply ignore half of the array based on whether the number we want is greater or smaller than the one at the middle of array. This is efficient because, after each comparison, we are eliminating half of the comparisons that we would have done if it were a linear search.

Which means, if we are sorting a considerably large array, insertion sort can be made even faster by doing a binary search when searching for the ideal position for next element in array. The only thing that we need to consider is, mostly the element we are searching won't be present in the partially sorted array and hence, instead of saying that the element was not found, our search should return the position where it would have ideally been found. And in case of a non existent element, that will happen when we reach the array of size 1.

Such an insertion sort algorithm that uses binary search to search for an ideal position for each element while searching is called binary insertion sort.

I hope this gave you a clear idea of how Binary search helped us achieve a search algorithm which is slightly faster than the plane old insertion sort.

As usual, comments/appreciation/criticism (a constructive one of course) everything is most welcome and appreciated.

Until then,

Happy Learning!

Banyan Bat