Just thinking, won't change complexity, but it could make sense to try and always choose your pivot at the front of a cache-line when possible and then choose this added pivot at then end of the cache line. Probably would only be worth it if the elements in the array numbers or tightly packed structs, and not just pointers to some allocated object elsewhere.