Subject: bug#54532: [PATCH] sorting

From: Lars Ingebrigtsen <[email-masked]>
Date: Wed, 23 Mar 2022 13:02:26 +0100

Andrew Cohen <[email-masked]> writes:

> |                                     | oldlist | oldvec |  tim |
> | (make-random-list 10000)            |    2790 |   2123 | 1557 |
> | (nreverse (make-sorted-list 10000)) |    1417 |    987 |  118 |
> | (make-sorted-list 10000)            |    1310 |    899 |  116 |
> | (make-swapped-list 10000 3)         |    1457 |   1019 |  122 |
> | (make-plus-list 10000)              |    1309 |    899 |  119 |
> | (make-onepercent-list 10000)        |    1764 |   1272 |  183 |
> | (make-constant-list 10000)          |    1292 |    888 |  116 |
> | (make-evil-list 10000)              |    1374 |    946 |  398 |
> | (make-block-list 10000 100)         |    2235 |   1646 |  919 |
> | (make-block-list 10000 10)          |    2598 |   1962 | 1451 |

Wow, great!  A tenfold speed increase on (mostly-)sorted lists (which is a
common use case in my experience) is impressive.

Reading the code, I don't really have any comments (but then again, I
don't really understand the timsort algorithm anyway).

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no