Skipping The Equal Keys

This is the Hoare-style partition from Sedgewick, whose scans deliberately stop on keys equal to the pivot.

int partition(std::vector<int> &a, int lo, int hi) {
    int v = a[lo], i = lo, j = hi + 1;
    while (true) {
        while (a[++i] < v) if (i == hi) break;   // stops on >= v
        while (v < a[--j]) if (j == lo) break;   // stops on <= v
        if (i >= j) break;
        std::swap(a[i], a[j]);
    }
    std::swap(a[lo], a[j]);
    return j;
}

A teammate changes both scan tests to a[++i] <= v and v <= a[--j], arguing that keys equal to the pivot are already in place so swapping them is wasted work. The build then times out on a 1,000,000-element array in which every value is the same. What happened?

It got faster but lost stability, and the timeout comes from the extra bookkeeping needed to restore stable order

Every partition now peels off exactly one element, so the sort makes about $n^2$ comparisons instead of about $n \lg n$

Nothing changed algorithmically; on an all-equal array both versions do the same work, so the timeout is caused by something else

The scans run past the ends of the array and the program reads out of bounds