sort_with_progress.cpp

#include <algorithm>
#include <random>
#include <vector>
#include <chrono>

template<typename RandomAccessIterator, typename Order, typename Reporter>
void sort_with_progress(RandomAccessIterator first, RandomAccessIterator last, Order order, const size_t &total, size_t &progress, Reporter report)
{
    if (last - first > 1)
    {
        // RandomAccessIterator middle = std::midpoint(first, last);
        RandomAccessIterator middle = first + (last - first) / 2;
        sort_with_progress(first, middle, order, total, progress, report);
        sort_with_progress(middle, last, order, total, progress, report);
        std::inplace_merge(first, middle, last, order);

        progress++;
        if (total < 100 || progress % (total / 100)==0)
        {
            report(100.0f * progress / total);
        }
    }
}

template<typename RandomAccessIterator, typename Reporter>
void sort_with_progress(RandomAccessIterator first, RandomAccessIterator last, Reporter report)
{
    size_t total = last - first;
    size_t progress = 0;
    // report(0.0f);
    sort_with_progress(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>(), total, progress, report);
    report(100.0f);
}

class stopwatch
{
public:
    stopwatch()
    {
        start = now_ms();
    }
    ~stopwatch()
    {
        auto ms = now_ms() - start;
        printf("use %lldms\n", ms);
    }
private:
    uint64_t now_ms()
    {
        using namespace std::chrono;
        auto now = high_resolution_clock::now();
        return duration_cast<milliseconds>(now.time_since_epoch()).count();
    }
    uint64_t start;
};

int main()
{
    std::vector<int> v;
    for(int i=0;i<10000*10;i++)
    {
        v.push_back(i);
    }

    std::random_device rng;
    std::mt19937 urng(rng());
    std::shuffle(v.begin(), v.end(), urng);


    {
        stopwatch sw;
        std::sort(v.begin(), v.end());
    }
    for(int i=0;i<10;i++)
    {
        printf("%d ", v[i]);
    }
    printf("\n");

    std::shuffle(v.begin(), v.end(), urng);

    {
        stopwatch sw;
        sort_with_progress(v.begin(), v.end(), [](double progress) {
            printf("report %.1f\n", progress);
        });
    }
    for(int i=0;i<10;i++)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
    return 0;
}