25

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.

4
  • 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
    Commented Aug 2, 2013 at 16:52
  • 9
    The 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. Commented Aug 2, 2013 at 16:52
  • @Derrek Whistle : answer updated Commented Aug 2, 2013 at 18:47
  • Reopened because the "duplicate" doesn't seem to mention number of comparisons or running time at all. Commented Jun 24, 2017 at 2:32

5 Answers 5

32

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

9
  • 10
    It still doesn't explain why it's actually O(n^2), and Wikipedia doesn't cite a source for that sentence.
    – seldon
    Commented May 21, 2018 at 11:48
  • 1
    @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. Commented May 21, 2018 at 12:25
  • 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.
    – seldon
    Commented May 21, 2018 at 14:39
  • 2
    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. Commented Jun 11, 2018 at 21:12
  • but as wiki said we cannot random access to perform binary search on linked list
    – Gintama
    Commented Aug 8, 2018 at 22:09
10

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.

4
  • 6
    if you use a balanced binary tree as data structure, both operations are O(log n). Commented Aug 2, 2013 at 21:29
  • 11
    But then, you've just implemented heap sort. Commented Aug 1, 2016 at 23:12
  • 1
    @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
    Commented Jul 28, 2017 at 8:47
  • @OscarSmith, If you use a tree as a data structure, you would have implemented a binary search tree not a heap sort.
    – sayem siam
    Commented Mar 25, 2021 at 15:10
6

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.

2

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.

3
  • 2
    insertion 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 :/ Commented Aug 2, 2013 at 23:27
  • 2
    That's a funny answer, sort a sorted array.
    – dud3
    Commented Jan 12, 2017 at 19:50
  • the worst case is if you are already sorted for many sorting algorithms and it isn't funny at all, sometimes you are asked to sort user input which happens to already be sorted. +1
    – Coder
    Commented Dec 25, 2020 at 3:20
0

For comparisons we have log n time, and swaps will be order of n. For n elements in worst case : n*(log n + n) is order of n^2.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.