Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
(Go solution) |
(→{{header|C++}}: Using std::upper_bound keeps this sort stable in the presence of equal keys and may be faster.) |
||
| Line 221: | Line 221: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
Uses binary search via std:: |
Uses binary search via std::upper_bound() to find the insertion position in logarithmic time, then performs the insertion via std::rotate(), in linear time. |
||
<lang cpp>#include <algorithm> |
<lang cpp>#include <algorithm> |
||
| Line 229: | Line 229: | ||
{ |
{ |
||
for (Iter i = beg; i != end; ++i) |
for (Iter i = beg; i != end; ++i) |
||
std::rotate(std:: |
std::rotate(std::upper_bound(beg, i, *i), i, i+1); |
||
}</lang> |
}</lang> |
||