Insertion Sort with binary search
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
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. |=^)