Rosetta Code

Sorting algorithms/Insertion sort: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Sonia (talk | contribs)
1,707 edits
Go solution
→‎{{header|C++}}: Using std::upper_bound keeps this sort stable in the presence of equal keys and may be faster.
Line 221:
 
=={{header|C++}}==
Uses binary search via std::lower_boundupper_bound() to find the insertion position in logarithmic time, then performs the insertion via std::rotate(), in linear time.
 
<lang cpp>#include <algorithm>
Line 229:
{
for (Iter i = beg; i != end; ++i)
std::rotate(std::lower_boundupper_bound(beg, i, *i), i, i+1);
}</lang>
 
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort"