I'm using stable_sort to sort a large vector.

The sorting takes on the order of a few seconds (say, 5-10 seconds), and I would like to display a progress bar to the user showing how much of the sorting is done so far.

But (even if I was to write my own sorting routine) how can I tell how much progress I have made, and how much more there is left to go?

I don't need it to be exact, but I need it to be "reasonable" (i.e. reasonably linear, not faked, and certainly not backtracking).