Ron <rjpeace@xxxxxxxxxxxxx> writes: > How are we choosing our pivots? See qsort.c: it looks like median of nine equally spaced inputs (ie, the 1/8th points of the initial input array, plus the end points), implemented as two rounds of median-of-three choices. With half of the data inputs zero, it's not too improbable for two out of the three samples to be zeroes in which case I think the med3 result will be zero --- so choosing a pivot of zero is much more probable than one would like, and doing so in many levels of recursion causes the problem. I think. I'm not too sure if the code isn't just being sloppy about the case where many data values are equal to the pivot --- there's a special case there to switch to insertion sort, and maybe that's getting invoked too soon. It'd be useful to get a line-level profile of the behavior of this code in the slow cases... regards, tom lane
