Hacker News Reader

Comment by alexh | Hacker News Reader

I read the documentation he linked to. It seems odd to me that there was no mention of a N-Pivot quicksort. Unless I missed it. It seems like the burden would be on proving that 2 was the optimal value of N

View on HN

You can make a quicksortish sort algorithm with N log N worst case by letting the number of pivots increase with N. (Details and proof, of course, in Knuth. The details are nontrivial but not all that painful.) I don't think anyone's ever proposed that that's worth doing in practice.

Using more pivots is going to make the code more complicated. The benefits of moving from one pivot to two seem to be real but not enormous; I'd be pretty surprised if moving to three pivots produced benefits worth the cost. But of course that's just handwaving, and indeed it would be interesting to measure.

My copy of Knuth does only mention that algorithm with a reference to a 1970 paper.

But what I woukd find more intereting is how the parallelizable Batcher and Pratt algorithms decsribed by Knuth fare on modern multicore machines with their weird cache hierarchies.

With two pivots, you can start the partitioning at either end and have a well defined location for each of the three partitions (at the top, at the botton, and inbetween). With more than three partitions, you would not know where to put the second to second last border without first sorting the array. You could just guess, but that would probably result in quite a lot of additional array shifting (lucky if you have a dedicated blitter chip for that :-)).

Having N > 2 will require you to do a sort on the pivots :P Also you will require that the array size be at least N. N = 2 is a perfect size --

size = 0 -> no sort

size = 1 -> no sort

size = 2 -> pivots can be made, thus can be sorted

etc.

Having N > 1 requires you to do a sort on the pivots. From the algorithm:

  3. P1 must be less than P2, otherwise they are swapped.

If you determine the number of pivots when you write the algorithm, they could be sorted in constant time. It would just require a lot of if-else branching...

Reply on news.ycombinator.com