Tom Lane <tgl@sss.pgh.pa.us> writes:
> Greg Stark <gsstark@mit.edu> writes:
> > That looks better both on average and in the worst case. Are the time
> > constants that much worse that the merge sort still takes longer?
>
> Keep in mind that this is only counting the number of
> comparison-function calls; it's not accounting for any other effects.
> In particular, for a large sort operation quicksort might win because of
> its more cache-friendly memory access patterns.
My question explicitly recognized that possibility. I'm just a little
skeptical since the comparison function in Postgres is often not some simple
bit of tightly optimized C code, but rather a complex locale sensitive
comparison function or even a bit of SQL expression to evaluate.
Cache effectiveness is may be a minimal factor anyways when the comparison is
executing more than a minimal amount of code. And one extra comparison is
going to cost a lot more too.
--
greg