Insertion Sort with binary search

Question

When implementing Insertion Sort, a binary search could be used to locate the position within the first i - 1 elements of the array into which element i should be inserted.

How would this affect the number of comparisons required? How would using such a binary search affect the asymptotic running time for Insertion Sort?

I'm pretty sure this would decrease the number of comparisons, but I'm not exactly sure why.

Answer 1

Straight from Wikipedia:

If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side-by-side), then using binary insertion sort may yield better performance. Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2(n)⌉ comparisons in the worst case, which is O(n log n). The algorithm as a whole still has a running time of O(n2) on average because of the series of swaps required for each insertion.

Source:

http://en.wikipedia.org/wiki/Insertion_sort#Variants

Here is an example:

http://jeffreystedfast.blogspot.com/2007/02/binary-insertion-sort.html

I'm pretty sure this would decrease the number of comparisons, but I'm not exactly sure why.

Well, if you know insertion sort and binary search already, then its pretty straight forward. When you insert a piece in insertion sort, you must compare to all previous pieces. Say you want to move this [2] to the correct place, you would have to compare to 7 pieces before you find the right place.

[1][3][3][3][4][4][5] ->[2]<- [11][0][50][47]

However, if you start the comparison at the half way point (like a binary search), then you'll only compare to 4 pieces! You can do this because you know the left pieces are already in order (you can only do binary search if pieces are in order!).

Now imagine if you had thousands of pieces (or even millions), this would save you a lot of time. I hope this helps. |=^)

Answer 2

If you have a good data structure for efficient binary searching, it is unlikely to have O(log n) insertion time. Conversely, a good data structure for fast insert at an arbitrary position is unlikely to support binary search.

To achieve the O(n log n) performance of the best comparison searches with insertion sort would require both O(log n) binary search and O(log n) arbitrary insert.

Answer 3

Binary Insertion Sort - Take this array => {4, 5 , 3 , 2, 1}

Now inside the main loop , imagine we are at the 3rd element. Now using Binary Search we will know where to insert 3 i.e. before 4.

Binary Search uses O(Logn) comparison which is an improvement but we still need to insert 3 in the right place. For that we need to swap 3 with 5 and then with 4.

Due to insertion taking the same amount of time as it would without binary search the worst case Complexity Still remains O(n^2). I hope this helps.