Let's consider a collection of elements with a descending sequence, a plateau, and a descending sequence again. Currently, if vergesort jumps into the plateau, it will consider it to be an ascending sequence, even though it's merely in the middle of a descending sequence, which means that it will consider a sequence as the one described above to be a descending sequence followed by an ascending sequence followed by another descending sequence, instead of considering it to be a big sequence.
Unfortunately, when encountering a plateau, the algorithm can't tell right away whether it's in an ascending or a descending sequence, so we'd need to expand the iterators on both sides until it finds an ascending or descending sequence. Doing so would require two comparisons instead of one to ensure that it's neither ascending nor descending, which would become a bit expensive. I guess that it can't reasonably be done without cheap trinary comparators.
Now, if the plateau could be part of a big ascending sequence and of a big descending sequence at once, how would we handle that? ...
Let's consider a collection of elements with a descending sequence, a plateau, and a descending sequence again. Currently, if vergesort jumps into the plateau, it will consider it to be an ascending sequence, even though it's merely in the middle of a descending sequence, which means that it will consider a sequence as the one described above to be a descending sequence followed by an ascending sequence followed by another descending sequence, instead of considering it to be a big sequence.
Unfortunately, when encountering a plateau, the algorithm can't tell right away whether it's in an ascending or a descending sequence, so we'd need to expand the iterators on both sides until it finds an ascending or descending sequence. Doing so would require two comparisons instead of one to ensure that it's neither ascending nor descending, which would become a bit expensive. I guess that it can't reasonably be done without cheap trinary comparators.
Now, if the plateau could be part of a big ascending sequence and of a big descending sequence at once, how would we handle that? ...