| 6256 | |
| 6257 | template<typename I, typename Pred> |
| 6258 | void median(I first, I middle, I last, const Pred& pred) |
| 6259 | { |
| 6260 | if (last - first <= 40) |
| 6261 | { |
| 6262 | // median of three for small chunks |
| 6263 | median3(first, middle, last, pred); |
| 6264 | } |
| 6265 | else |
| 6266 | { |
| 6267 | // median of nine |
| 6268 | size_t step = (last - first + 1) / 8; |
| 6269 | |
| 6270 | median3(first, first + step, first + 2 * step, pred); |
| 6271 | median3(middle - step, middle, middle + step, pred); |
| 6272 | median3(last - 2 * step, last - step, last, pred); |
| 6273 | median3(first + step, middle, last - step, pred); |
| 6274 | } |
| 6275 | } |
| 6276 | |
| 6277 | template<typename I, typename Pred> |
| 6278 | void sort(I begin, I end, const Pred& pred) |