How to figure out "progress" while sorting?

Split the vector into several equal sections, the quantity depending upon the granularity of progress reporting you desire. Sort each section seperately. Then start merging with std::merge. You can report your progress after sorting each section, and after each merge. You'll need to experiment to determine how much percentage the sorting of the sections should be counted compared to the mergings.

Edit:

I did some experiments of my own and found the merging to be insignificant compared to the sorting, and this is the function I came up with:

template<typename It, typename Comp, typename Reporter>
void ReportSort(It ibegin, It iend, Comp cmp, Reporter report, double range_low=0.0, double range_high=1.0)
{
    double range_span = range_high - range_low;
    double range_mid = range_low + range_span/2.0;
    using namespace std;
    auto size = iend - ibegin;
    if (size < 32768) {
       stable_sort(ibegin,iend,cmp);        
    } else {
        ReportSort(ibegin,ibegin+size/2,cmp,report,range_low,range_mid);
        report(range_mid);
        ReportSort(ibegin+size/2,iend,cmp,report,range_mid,range_high);
        inplace_merge(ibegin, ibegin + size/2, iend);
    }   
}

int main()
{
    std::vector<int> v(100000000);
    std::iota(v.begin(), v.end(), 0);
    std::random_shuffle(v.begin(), v.end());

    std::cout << "starting...\n";

    double percent_done = 0.0;
    auto report = [&](double d) {
        if (d - percent_done >= 0.05) {
            percent_done += 0.05;
            std::cout << static_cast<int>(percent_done * 100) << "%\n";
        }
    };
    ReportSort(v.begin(), v.end(), std::less<int>(), report);
}

Standard library sort uses a user-supplied comparison function, so you can insert a comparison counter into it. The total number of comparisons for either quicksort/introsort or mergesort will be very close to log₂N * N (where N is the number of elements in the vector). So that's what I'd export to a progress bar: number of comparisons / N*log₂N

Since you're using mergesort, the comparison count will be a very precise measure of progress. It might be slightly non-linear if the implementation spends time permuting the vector between comparison runs, but I doubt your users will see the non-linearity (and anyway, we're all used to inaccurate non-linear progress bars :) ).

Quicksort/introsort would show more variance, depending on the nature of the data, but even in that case it's better than nothing, and you could always add a fudge factor on the basis of experience.

A simple counter in your compare class will cost you practically nothing. Personally I wouldn't even bother locking it (the locks would hurt performance); it's unlikely to get into an inconsistent state, and anyway the progress bar won't go start radiating lizards just because it gets an inconsistent progress number.