Re: BUG #12866: Another performance problem with intarray extenstion operators

maxim.boguk@gmail.com writes:
> I found second case where intarray operators have serious performance
> issues:
> ...
> PS: filling array in descending order is critical to reproducing the issue.

The problem is evidently in isort():

    /*
     * We use a simple insertion sort.  While this is O(N^2) in the worst
     * case, it's quite fast if the input is already sorted or nearly so.
     * Also, for not-too-large inputs it's faster than more complex methods
     * anyhow.
     */

That comment, as well as the current code, date to my commit fdf2dbda;
but it doesn't look like the previous code was any better in terms of
worst-case behavior.  It's tempting to just trash the whole thing in
favor of qsort().

            regards, tom lane