Put the values below a pivot first, then the ones equal to it, then the ones above, in one pass and in place: three indices keep four regions, and each step shrinks the unknown one. n comparisons, against two passes and n extra slots for counting then rewriting.
This interactive visualization needs JavaScript.