| 6149 | |
| 6150 | template<typename I, typename Pred, typename T> |
| 6151 | void insertion_sort(I begin, I end, const Pred& pred, T*) |
| 6152 | { |
| 6153 | assert(begin != end); |
| 6154 | |
| 6155 | for (I it = begin + 1; it != end; ++it) |
| 6156 | { |
| 6157 | T val = *it; |
| 6158 | |
| 6159 | if (pred(val, *begin)) |
| 6160 | { |
| 6161 | // move to front |
| 6162 | copy_backwards(begin, it, it + 1); |
| 6163 | *begin = val; |
| 6164 | } |
| 6165 | else |
| 6166 | { |
| 6167 | I hole = it; |
| 6168 | |
| 6169 | // move hole backwards |
| 6170 | while (pred(val, *(hole - 1))) |
| 6171 | { |
| 6172 | *hole = *(hole - 1); |
| 6173 | hole--; |
| 6174 | } |
| 6175 | |
| 6176 | // fill hole with element |
| 6177 | *hole = val; |
| 6178 | } |
| 6179 | } |
| 6180 | } |
| 6181 | |
| 6182 | // std variant for elements with == |
| 6183 | template<typename I, typename Pred> |
no test coverage detected