Sorting algorithms/Insertion sort: Difference between revisions

FasterUses thanbinary the basic algorithmsearch becausevia std::lower_bound() findsto find the insertion position in logarithmic time., Insertionthen itself,performs performedthe insertion withvia std::rotate(), is stillin linear time.

for (std::vector<int>::iteratorIter i =v.begin() beg; i !=v. end(); ++i)

std::rotate(std::lower_bound(v.begin()beg, i, *i), i, i+1);