How to monitor/show progress during a C++ sort

I would recommend your second option: use std::sort or another standard sorting function like qsort, and have the comparator report its progress. But don't update in every comparison--that would be unbearably slow--instead update every (say) 100ms.

I think, even if you wrote your own sort, that you would have to do a lot of careful measurement if you wanted the progress indicator to be accurate. If you only want an approximate progress indicator, then you can use some metric like 'average distance between compared elements' or 'number of comparisons as compared to average expected number for quicksort' as your metric and implement the comparison idea you already mentioned.

And yes, I assume that you aren't a complete idiot and do not plan on updating the progress indicator at each and every comparison. If you did that you'd spend much more time indicating progress than sorting.

As an example, you would generally expect about n log2 n operations for quicksort. The analysis of how many comparisons are involved is more detailed and can be more accurate than that general measure, but for the purposes of this example, lets just assume. So you could count comparisons and report number_of_comparisons / (n log2 n) as your estimate of progress.

Since that's just an average indicator I would run a few experiments and see how far your estimate is off, and throw in some fudge factors to make it line up with the average expected case. You could also have a progress bar that indicated the uncertainty by having sort of "This is where I think I'll be done." indicator and some space after the indicator.

Even if you used your own sort and came up with a more seemingly precise measure, the progress bar still wouldn't update smoothly and the effect would be similar. The only way you know for sure how long your sort is going to take is if you use a somewhat slower, but really predictable sort, in which case you can predict how long it will take from the number of elements, or use a really fast sort that has less predictable behavior in specific cases, in which case there is no real way to have a perfectly accurate progress bar.

Predictability of subtasks and predictability of total number of comparisons are strongly linked. So I really don't think that subtasks make a better measure than total number of comparisons.

If you want to use your own sort and predictability is your highest goal, go for heapsort. It's still an O(n log2 n) sort, and it's close to being a minimum comparison sort (or so I remember from reading Knuth). It also takes a very predictable amount of time to complete regardless of the dataset its fed. It's one of the slower O(n log2 n) sorts, but still.

As one of your commenters mentioned though, you might be solving a problem that doesn't actually exist. Run some experiments first. The problem is a fun intellectual challenge regardless of its usefulness though. :-)

Since std::sort is template based, the source should be available in a header. You can make a copy of it and insert your progress callback. The big problem will be predicting how close you are to completion - most sort functions will be based on Quicksort, which doesn't always do the same number of comparisons.

Writing your own Merge sort would be a possibility; the algorithm is easy and the number of steps are well defined.