hpx: parallel merge is not stable

merge_testcase.zip The documentation for the merge algorithm states For equivalent elements in the original two ranges, the elements from the first range precede the elements from the second range. I find that this is sometimes not the case when the parallel execution policy is chosen.

The attached testcase merges two ranges of <int, char> pairs, ordered by the first value. For my compiler (gcc 6.3.0) I find that the resulting merged sequence interleaves equivalent elements from the input ranges, instead of using all of the equivalent elements from the first range first. Specifically, when merging (3,a), (3,b) with (3,c) the result is (3,a), (3,c), (3,b).

Due to the high threshold (65536) for using the parallel version of the algorithm, reproducing this requires modifying this line so the threshold is something low (I used 10).