Re: Which qsort is used

Marko Kreen <markokr@gmail.com> writes:
> http://sourceware.org/ml/libc-alpha/2000-03/msg00139.html
> Seems glibc guys once tested some implementation of quicksort vs. merge sort
> and found out that
>    "For small sets and smaller data types (arrays of ints and
>    arrays of doubles) mergesort is definitly faster and behaves better."

> If the qsort in Postgres is called usually on wide data - on full rows
> not on pointers to rows, then indeed it would be wise to use out own
> sort.

But I can assure you that it is never called on any such thing.  Since
qsort only works on fixed-size items, it'd be essentially impossible
to use it directly on rows; we *always* use it on pointers instead.
(We could only do the other if we had a separate code path for rows
containing only fixed-width-never-null columns, which we do not, and
it'd be pretty silly to add one in view of the increased data-copying
work that would result.)

The referenced message is pretty interesting for this discussion,
particularly its pointer to someone's sort test routines --- wonder
if those are still available?  It was also eye-opening to read that
glibc actually contains two separate algorithms to use depending on
the size of the target array.  If that's still true then it throws a
lot of the testing so far into doubt.
        regards, tom lane