Interruptible sort function

Question

In my application I need to sort a rather large array, which turns out to be a standard task using, e.g. std::sort.

Being situated in a GUI application I'd like to give some sort of response on the progress of the sorting. My first attempt is to figure out the approximate number of comparisons needed (n*log2(n) for std::sort) and then simply counting them in the comparison functor passed to std::sort. This works quite well.

The sorting algorithm is executed in a separate thread to keep the GUI responsive. It communicates its progress to the GUI using Qt's signals or some similar thread safe mechanism.

However, I'd also like to have the sort operation interruptible. That is, the user is provided a button or something similar to abort the whole operation. At the moment I only see two options:

1. Preemptively terminate the thread (pthread_cancel etc.)
2. rewrite the sorting algorithm and insert explicit cancellation points.

Considering thread cancellation rather as a last resort and refusing to rewrite standard library algorithms, I'm holding the wolf by the ears.

Answer 1

Have the comparison function check an atomic flag and throw an exception if the flag is set. The sorting thread should catch the exception and exit cleanly. The GUI thread then just needs to set the flag.