Re: sorting in C

[Eli Zaretskii <eliz@gnu.org>]

> From: Andrew Cohen <acohen@ust.hk>
> Date: Fri, 04 Mar 2022 08:13:33 +0800
> 
> |                                     | oldlist | oldvec |  tim |       |
> |-------------------------------------+---------+--------+------+------|
> | (make-random-list 10000)            |    2842 |   2146 | 2233 |  27% |
> | (nreverse (make-sorted-list 10000)) |    1431 |   1004 |  174 | 722% |
> | (make-sorted-list 10000)            |    1333 |    924 |  170 | 684% |
> | (make-swapped-list 10000 3)         |    1512 |   1055 |  179 | 745% |
> | (make-plus-list 10000)              |    1346 |    915 |  174 | 674% |
> | (make-onepercent-list 10000)        |    1792 |   1308 |  274 | 554% |
> | (make-constant-list 10000)          |    1328 |    917 |  169 | 686% |
> | (make-evil-list 10000)              |    1398 |    969 |  609 | 130% |
> | (make-block-list 10000 100)         |    2244 |   1651 | 1304 |  72% |
> | (make-block-list 10000 10)          |    2641 |   1990 | 2034 |  30% |
> 
> As you can see the worst case is purely random for which the new
> algorithm is still more than 25% faster than the current one (albeit 4%
> slower than for vectors in this case), and short blocks is a close
> second. Everything else is clearly much faster, with almost everything
> else being factors of 6 to 8 times faster.

Yes, this looks very promising, thanks.

> I'll post again in awhile with final questions and some suggestions for
> pushing it to git. Please let me know if I should post the code here
> (its about 1K lines including lots of comments.)

I think it is best to send your changes as "git format-patch" in a
message submitted to bug-gnu-emacs@gnu.org, which will then create an
issue on our issue tracker.  That will ensure this is not forgotten by
some chance.

Then we will wait for the completion of your legal paperwork.

Thanks.