| 250 | |
| 251 | protected: |
| 252 | void Run(CppBenchmark::Context& context) override |
| 253 | { |
| 254 | // Generate items to sort |
| 255 | std::generate(items.begin(), items.end(), rand); |
| 256 | |
| 257 | // Use temporary array |
| 258 | std::vector<int> temp(items.size()); |
| 259 | |
| 260 | // Start from the chunk size 1 |
| 261 | size_t chunk = 1; |
| 262 | // While chunk size less than count of items |
| 263 | while (chunk < items.size()) |
| 264 | { |
| 265 | // Perform merge operation for the current chunks |
| 266 | for (size_t i = 0; i < items.size(); i += 2 * chunk) |
| 267 | MergeSortInternal(temp.data() + i, items.data() + i, i, items.size(), chunk); |
| 268 | // Increase chunk size |
| 269 | chunk *= 2; |
| 270 | // Swap arrays |
| 271 | std::swap(temp, items); |
| 272 | } |
| 273 | context.metrics().AddItems(items.size()); |
| 274 | } |
| 275 | |
| 276 | private: |
| 277 | static void MergeSortInternal(int* dst, int* src, size_t index, size_t size, size_t chunk) |