Class MergeSort

examples/sort.cpp:246–306

};

class MergeSort : public CppBenchmark::Benchmark, public SortFixture
{
public:
    using Benchmark::Benchmark;

protected:
    void Run(CppBenchmark::Context& context) override
    {
        // Generate items to sort
        std::generate(items.begin(), items.end(), rand);

        // Use temporary array
        std::vector<int> temp(items.size());

        // Start from the chunk size 1
        size_t chunk = 1;
        // While chunk size less than count of items
        while (chunk < items.size())
        {
            // Perform merge operation for the current chunks
            for (size_t i = 0; i < items.size(); i += 2 * chunk)
                MergeSortInternal(temp.data() + i, items.data() + i, i, items.size(), chunk);
            // Increase chunk size
            chunk *= 2;
            // Swap arrays
            std::swap(temp, items);
        }
        context.metrics().AddItems(items.size());
    }

private:
    static void MergeSortInternal(int* dst, int* src, size_t index, size_t size, size_t chunk)
    {
        size_t index1 = 0;
        size_t index2 = 0;

        while ((index1 < chunk) || (index2 < chunk))
        {
            // Check bounds of left chunk
            if ((index + index1 >= size))
                index1 = chunk;
            // Check bounds of right chunk
            if (index + chunk + index2 >= size)
                index2 = chunk;

            // Check if we use right or left chunk for merge
            if ((index2 < chunk) && ((index1 == chunk) || (src[chunk + index2] < src[index1])))
            {
                // Use right chunk
                *dst++ = src[chunk + index2];
                ++index2;
            }
            else if (index1 < chunk)
            {
                // Use left chunk
                *dst++ = src[index1];
                ++index1;
            }