I have been trying to speed up some things in gnus, with some
success. But it inspired me to take a look at the sorting algorithm
in C.  I have done some simple tests and have made some (simple)
improvements which I hope to push. But I am a novice at the C parts of
emacs (and C in general) so am sharing here.

Currently, lists and vectors have different code paths, but both use a
recursive merge sort (I haven't actually looked at the vector code, I'm
just guessing from the function names). There are some minor
inefficiencies in the list code (it computes the length of the list on
each recursion, for example, rather than passing it as an
argument---changing this alone gives a 10% speedup) which I played
with. I also tried an iterative rather than recursive merge (no real
improvement). But in the end I found that the simplest large improvement
was to:

1. Use an iterative insertion sort for small lists (length < 64). I
   wrote one that is in-place and does minimal work when the list is
   sorted or reverse sorted, which is the case for much of the sorting
   in gnus.
2. Convert longer lists to a vector, hand it off to the vector code, and
   convert back to a list. This gives a 35% improvement in all cases I
   was able to test.

These are the parts I propose pushing (patch attached). But then I:

3. Replaced the current vector sorting algorithm with TIMSORT. This did
   exactly what TIMSORT is supposed to do: on random data it is
   marginally slower than the current mergesort. But on partially
   ordered data it is 5 times faster.

I plan to continue playing with changes to the vector algorithm to see
what other changes might be worthwhile.

Best,
Andy