La clasificación de biblioteca estándar utiliza una función de comparación proporcionada por el usuario, por lo que puede insertar un contador de comparación en ella. El número total de comparaciones para quicksort/introsort o mergesort estará muy cerca de log2 N * N (donde N es el número de elementos en el vector). Eso es lo que exportaría a una barra de progreso:número de comparaciones / N*log2 N
Dado que está utilizando mergesort, el recuento de comparación será una medida muy precisa del progreso. Puede ser ligeramente no lineal si la implementación dedica tiempo a permutar el vector entre ejecuciones de comparación, pero dudo que sus usuarios vean la no linealidad (y de todos modos, todos estamos acostumbrados a barras de progreso no lineales inexactas :)).
Quicksort/introsort mostraría más variación, dependiendo de la naturaleza de los datos, pero incluso en ese caso es mejor que nada, y siempre se puede agregar un factor de error en función de la experiencia.
Un contador simple en su clase de comparación no le costará prácticamente nada. Personalmente, ni siquiera me molestaría en bloquearlo (los bloqueos dañarían el rendimiento); es poco probable que entre en un estado inconsistente y, de todos modos, la barra de progreso no comenzará a emitir lagartijas solo porque obtiene un número de progreso inconsistente.