| 24 | // here to keep the correspondence with the article about Skew|DC3. |
| 25 | template <typename Values> |
| 26 | void RadixSort(size_t numKeys, size_t const * keys, size_t numValues, Values const & values, size_t * resultKeys) |
| 27 | { |
| 28 | std::vector<size_t> count(numValues, 0); |
| 29 | for (size_t i = 0; i < numKeys; ++i) |
| 30 | { |
| 31 | auto const value = values[keys[i]]; |
| 32 | ASSERT_LESS(value, count.size(), ()); |
| 33 | ++count[value]; |
| 34 | } |
| 35 | for (size_t i = 1; i < numValues; ++i) |
| 36 | count[i] += count[i - 1]; |
| 37 | for (size_t i = numKeys - 1; i < numKeys; --i) |
| 38 | resultKeys[--count[values[keys[i]]]] = keys[i]; |
| 39 | } |
| 40 | |
| 41 | bool InLeftHalf(size_t middle, size_t pos) |
| 42 | { |