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.

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