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:

Preemptively terminate the thread (pthread_cancel etc.)
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.

How about using e.g. [`std::async`](http://en.cppreference.com/w/cpp/thread/async) with the [`async` launch policy](http://en.cppreference.com/w/cpp/thread/launch), and if aborted just don't use the result? — Some programmer dude, Jan 07 '17 at 17:42
dude: I considered as a quite similar solution to simply _abandon_ the sorting thread, yes. But it keeps on eating CPU then :-) — Kamajii, Jan 07 '17 at 17:45
@ks1322: Great minds think alike - I hadn't seen your comment when I wrote my answer. — Martin Bonner supports Monica, Jan 07 '17 at 17:47

score 7 · Accepted Answer · answered Jan 07 '17 at 17:45

7

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.

answered Jan 07 '17 at 17:45

Martin Bonner supports Monica

28,528
3
51
88

also @ks1322: This is depressingly brilliant. For me, one reasonable application for exceptions at last... – Kamajii Jan 07 '17 at 17:51
There could be a potential issue that the array being sorted could be corrupted by an exception. std::sort may be safe since it's in place, but std::stable_sort or std::list::sort (usually variations of merge sort) may have some data stuck in temp buffers. – rcgldr Jan 09 '17 at 09:53
@rcgldr That sort of comes under the heading "if you are using exceptions, your code must be exception safe". At an absolute minimum objects must be left destructible; but you also need to ensure that any object which is not destroyed by the exception is left in a consistent state afterwards. – Martin Bonner supports Monica Jan 09 '17 at 10:06
@MartinBonner - this issue recently came up in the case of Visual Studio's std::list::sort. Take a look at [prior thread](http://stackoverflow.com/questions/40622430/stdlistsort-why-the-sudden-switch-to-top-down-strategy) about exception safety (specifically a compare that throws an exception). – rcgldr Jan 09 '17 at 10:26

Interruptible sort function

1 Answers1