| 6404 | } |
| 6405 | |
| 6406 | template <typename I, typename Pred, typename T> void insertion_sort(I begin, I end, const Pred& pred, T*) |
| 6407 | { |
| 6408 | assert(begin != end); |
| 6409 | |
| 6410 | for (I it = begin + 1; it != end; ++it) |
| 6411 | { |
| 6412 | T val = *it; |
| 6413 | |
| 6414 | if (pred(val, *begin)) |
| 6415 | { |
| 6416 | // move to front |
| 6417 | copy_backwards(begin, it, it + 1); |
| 6418 | *begin = val; |
| 6419 | } |
| 6420 | else |
| 6421 | { |
| 6422 | I hole = it; |
| 6423 | |
| 6424 | // move hole backwards |
| 6425 | while (pred(val, *(hole - 1))) |
| 6426 | { |
| 6427 | *hole = *(hole - 1); |
| 6428 | hole--; |
| 6429 | } |
| 6430 | |
| 6431 | // fill hole with element |
| 6432 | *hole = val; |
| 6433 | } |
| 6434 | } |
| 6435 | } |
| 6436 | |
| 6437 | // std variant for elements with == |
| 6438 | template <typename I, typename Pred> void partition(I begin, I middle, I end, const Pred& pred, I* out_eqbeg, I* out_eqend) |
no test coverage detected