2010-10-22, 12:43 AM
I don't know of any sequential data structure for which both insertion and random access (which is needed for the binary search you're describing) are O(1).
So assuming both ways of insertion sort are O(n^2)y its only real use is as a way to sort small data sets that is very simple to implement from scratch, so saving some time on the comparisons might not be worth complicating things when you could just use a better algorithm instead.
So assuming both ways of insertion sort are O(n^2)y its only real use is as a way to sort small data sets that is very simple to implement from scratch, so saving some time on the comparisons might not be worth complicating things when you could just use a better algorithm instead.