vkostyukov

These are very good questions. The thing is we actually stopped at two pivots. But you can try to obtain the recurrent relation for three pivots by you own using the steps provided in the post.

Having two pivots in Quicksort reduces the number of swaps (# of comparisons is the same).

I'm quite disappointed in people saying that I should have replaced recursion with iteration. That wasn't my goal - to tune a binary search algorithm. I've know the exact result of this research before writing post. I've already known that it gives you literally nothing in terms of performance. The only question I had is why is so? And I wanted to show how to combine math and complexity analysis in order to figure this out.

it's not about tuning something and getting gain (in business, in performance). It's about digging into the challenging problems and finding answers (and of course - having fun).

Think about why we split the input array into two equals parts? There is a nice question in Skiena's algorithms book: what would be with time complexity and algorithm itself if we split the array in two parts: 1/3 and 2/3. The best answer is for sure: "Dr. Skiena, are you simply stupid asking these questions? Just rewrite it with iterations instead and relax."