> Vadim-It would be very interesting if something along these lines could be made practical. It isn't obvious how to do step (3) in place. Either you end up allocating extra storage to do it, in which case you might as well have used a merge sort, or you end up doing some extra shuffling around of the data, in which case it is probably more expensive than the dual-partition version. Perhaps there is some technique I'm not thinking of.Cheers,Neal
I didn't think of space requirements, but naively it seems to me that the two-pivot method of categorizing the non-pivot elements in place (which admittedly I don't entirely understand) would work just as well with the m-pivot method.
