Question

Which of the following is an advantage of binary insertion sort over its standard version?

(a) it has better time complexity

(b) it has better space complexity

(c) it makes less number of comparisons

(d) it has no significant advantage

I got this question in examination.

This key question is from Sorting in division Sorting of Data Structures & Algorithms II

Answer 1

The correct option is (c) it makes less number of comparisons

Easy explanation - Binary insertion sort makes less number of comparisons as compared to the standard version of insertion sort. Binary insertion sort makes log n comparisons in the worst case as compared to n comparisons made in the standard version.