Initially, the gather algorithm is hard to grasp because it is very short but has a seemingly complex task. Therefore, let's step through it:

1. The initial state is a range of items, for which we present a predicate function. In the diagram, all items for which our predicate function returns true, are painted in gray. The iterators a and c mark the whole range, and iterator b points to a pivot element. The pivot element is the element around which we want to gather all the gray items.
2. The gather algorithm calls std::stable_partition on the range [a, b) and while doing that, it uses a negated version of the predicate. It negates the predicate because std::stable_partition moves all items for which the predicate returns true to the front. We want exactly the opposite to happen.

3. Another std::stable_partition call is done but, this time, on the range, [b, c), and without negating the predicate. The gray items are moved to the front of the input range, which means they are all moved towards the pivot element pointed at by b.
4. The items are now gathered around b and the algorithm returns iterators to the beginning and the end of the now consecutive range of gray items.

We called gather multiple times on the same range. At first, we gathered all the items around the middle of the range. Then we gathered the items around begin() and then around end() of the range. These cases are interesting because they always lead one of the std::stable_partition calls to operate on an empty range, which results in no action.

We did the last call to gather again with the parameters (begin, end, middle) of the range, and that did not work. Why? At first, this looks like a bug, but actually, it is not.

Imagine the character range, "aabb", together with a predicate function, is_character_a, which is only true for the 'a' items--if we call it with a third iterator pointing to the middle of the character range, we would observe the same bug. The reason is that the first stable_partition call would operate on the subrange, "aa", and the other stable_partition call operates on the range, "bb". This series of calls cannot result in "baab", which we initially naively hoped.

The gather_sort modification is basically the same as gather. The only difference is that it does not accept a unary predicate function but a binary comparison function, just like std::sort. And instead of calling std::stable_partition twice, it calls std::stable_sort twice.

The negation of the comparison function cannot be done with not_fn, just like we did in the gather algorithm because not_fn does not work on binary functions.