Insertion Sort with binary search

10

1

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.

Derrek Whistle

Posted 2013-08-02T16:47:11.787

Reputation: 321

Binary search the position takes O(log N) compares. This makes O(N.log(N)) comparisions for the hole sorting. [We can neglect that N is growing from 1 to the final N while we insert] – MrSmith42 – 2013-08-02T16:52:12.747

4The algorithm is still O(n^2) because of the insertions. So, whereas binary search can reduce the clock time (because there are fewer comparisons), it doesn't reduce the asymptotic running time. – Jim Mischel – 2013-08-02T16:52:58.280

@Derrek Whistle : answer updated – But I'm Not A Wrapper Class – 2013-08-02T18:47:26.507

Reopened because the "duplicate" doesn't seem to mention number of comparisons or running time at all. – Dukeling – 2017-06-24T02:32:27.833

Answers

16

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. |=^)

But I'm Not A Wrapper Class

Posted 2013-08-02T16:47:11.787

Reputation: 9 234

2It still doesn't explain why it's actually O(n^2), and Wikipedia doesn't cite a source for that sentence. – mattecapu – 2018-05-21T11:48:34.713

@mattecapu Insertion Sort is a heavily study algorithm and has a known worse case of O(n^2). Using Binary Search to support Insertion Sort improves it's clock times, but it still takes same number comparisons/swaps in worse case. Intuitively, think of using Binary Search as a micro-optimization with Insertion Sort. – But I'm Not A Wrapper Class – 2018-05-21T12:25:17.603

Right, I didn't realize you really need a lot of swaps to move the element. So the sentences seemed all vague. Sorry for the rudeness. – mattecapu – 2018-05-21T14:39:28.833

What if insertion sort is applied on linked lists then worse case time complexity would be (nlogn) and O(n) best case, this would be fairly efficient. – Deepak Yadav – 2018-06-11T21:12:40.647

but as wiki said we cannot random access to perform binary search on linked list – Gintama – 2018-08-08T22:09:28.460

I think the goal is to use an ArrayList or a dynamic array. This way you can apply both techniques (insertion and binary search) together. – But I'm Not A Wrapper Class – 2018-08-09T00:42:27.513

5

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.

Patricia Shanahan

Posted 2013-08-02T16:47:11.787

Reputation: 22 165

4if you use a balanced binary tree as data structure, both operations are O(log n). – Karoly Horvath – 2013-08-02T21:29:18.077

@KarolyHorvath True. – Patricia Shanahan – 2013-08-02T21:39:57.760

7But then, you've just implemented heap sort. – Oscar Smith – 2016-08-01T23:12:03.973

@OscarSmith but Heaps don't provide O(log n) binary search. At least neither Binary nor Binomial Heaps do that. The heaps only hold the invariant, that the parent is greater than the children, but you don't know to which subtree to go in order to find the element X in the heap, when it's smaller that the parent/root.

I would say, that HeapSort is an improvement of SelectionSort rather than the InsertionSort, since in Selection sort we are looking for the next biggest/smallest number in the subarray from [i:n-1], but heaps allow us to find the next max/min and remove it in O(log n) time – denis631 – 2017-07-28T08:47:50.680

1

Assuming the array is sorted (for binary search to perform), it will not reduce any comparisons since inner loop ends immediately after 1 compare (as previous element is smaller). In general the number of compares in insertion sort is at max the number of inversions plus the array size - 1.

Since number of inversions in sorted array is 0, maximum number of compares in already sorted array is N - 1.

WastedPandoo

Posted 2013-08-02T16:47:11.787

Reputation: 43

1insertion sort keeps the processed elements sorted. that doesn't mean that in the beginning the whole array is already sorted. if it were so, you wouldn't need sorting :/ – Karoly Horvath – 2013-08-02T23:27:12.943

1That's a funny answer, sort a sorted array. – dud3 – 2017-01-12T19:50:42.903