Insert Sort with binary search

Question

When implementing Sorting Sort, binary search can be used to determine the location in the first elements of the i-1 array into which the i element should be inserted.

How will this affect the number of comparisons? How would using such a binary search affect the asymptotic runtime for sorting the insert?

I'm sure this will reduce the number of comparisons, but I'm not quite 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 (for example, choosing one of the pairs displayed side by side), then using binary sorting of the insert can improve performance. Binary inserting uses binary search to determine the correct location to insert new elements and therefore performs log2 (n) ⌉ worst-case comparisons , which is O (n log n) . The whole algorithm still has O (n2) runtimes on average due to the series of swaps needed for each insert.

Source:

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

Here is an example:

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

I am sure that this will reduce the number of comparisons , but I am not quite sure why.

Well, if you already know insertion sorting and binary search, then this is pretty straight forward. When you insert a piece in an insertion sort, you must compare all the previous parts. Say that you want to move this [2] to the right place, you have to compare it with 7 parts before you find the right place.

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

However, if you start the comparison half way (for example, binary search), you will only compare 4 pieces! You can do this because you know that the left parts are already in order (you can only do a binary search if things are in order!).

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

Answer 2

If you have a good data structure for efficient binary search, it is unlikely that O (log n) input time will be set. Conversely, a good data structure for quick insertion at any position is unlikely to support binary search.

To achieve the O (n log n) performance of the best comparison with insertion sorting, you need both a binary search of O (log n) and O (log n).

Answer 3

Assuming the array is sorted (to perform a binary search), it will not reduce any comparisons, since the inner loop ends immediately after 1 comparison (since the previous element is smaller). In the general case, the number of comparisons in insertion sorting is equal to the maximum number of inversions plus the array size - 1.

Since the number of inversions in a sorted array is 0, the maximum number of comparisons in an already sorted array is N - 1.

Answer 4

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

Now inside the main loop, imagine that we are on the third element. Now with the help of binary search we will know where to insert 3, i.e. up to 4.

Binary search uses O (Logn) comparison, which is an improvement, but we still need to insert 3 in the right place. To do this, we need to change 3 from 5, and then from 4.

Due to the fact that the insertion takes as much time as without a binary search, in the worst case, the complexity still remains O (n ^ 2). Hope this helps.