Sort functions with specialized comparators

On Tue, Jan 7, 2025 at 12:59 PM Andrey M. Borodin <x4mmm(at)yandex-team(dot)ru>
wrote:
>
> I'm worried about another case that we cannot measure: PREPAREARR(a) on
empty array will return new array.

In theory, yes, but it doesn't happen in our regression tests, so it might
be worth looking into making that happen before worrying about it further.

https://coverage.postgresql.org/contrib/intarray/_int_tool.c.gcov.html#248

> And one more case.
> BTW for pre-sorted desc arrays desc sorting is slower:

Right, that's because the sort template special-cases pre-sorted input, and
that only works for descending input if the comparator is wired for
descending output. I'm still not in favor of having two separate
specializations because that's kind of a brute force approach, and even if
that's okay this is a strange place to set that precedent [*]. The
principled way to avoid this regression is to add a one-time check for
descending input in the template, which would be more widely beneficial. I
suspect (and I think the archives show others wondering the same) we could
make the ascending pre-check a one-time operation as well, but I'd need to
test.

[*] It's interesting to note that not terribly long ago isort was an
insertion sort, hence the name:

commit 8d1f239003d0245dda636dfa6cf0add13bee69d6
Author: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Date: Sun Mar 15 23:22:03 2015 -0400

Replace insertion sort in contrib/intarray with qsort().

--
John Naylor
Amazon Web Services

--
John Naylor
Amazon Web Services