...one of the most highly
regarded and expertly designed C++ library projects in the
world. — Herb Sutter and Andrei
is designed to run in linear time for a couple of best-case patterns. Linear
time is achieved for inputs that are in strictly ascending or descending
order, only contain equal elements, or are strictly in ascending order
followed by one out-of-place element. There are two seperate mechanisms
at play to achieve this.
For equal elements a smart partitioning scheme is used that always puts equal elements in the partition containing elements greater than the pivot. When a new pivot is chosen it's compared to the greatest element in the partition before it. If they compare equal we can derive that there are no elements smaller than the chosen pivot. When this happens we switch strategy for this partition, and filter out all elements equal to the pivot.
To get linear time for the other patterns we check after every partition if any swaps were made. If no swaps were made and the partition was decently balanced we will optimistically attempt to use insertion sort. This insertion sort aborts if more than a constant amount of moves are required to sort.