Comment by karmakaze

I would expect eliminating branches in a busy inner loop to matter.

The interesting part is how that was done:

> A New Primitive, swap_if

> How can we use this method in our sort? First, let us make a swap_if:

  inline bool swap_if(bool c, int& a, int& b) {
    int ta = a, mask = -c;  // false -> 0, true -> 111..111
    a = (b & mask) | (ta & ~mask);
    b = (ta & mask) | (b & ~mask);
    return c;
  }

> In our partition function, then, we can transform

    if (*right <= pivot) {
      int tmp = *left; *left = *right, *right = tmp;
      ++left;
    }

> into just

    left += swap_if(*right <= pivot, *left, *right);