Re: sorting in C

[Eli Zaretskii]

> From: Andrew Cohen <acohen@ust.hk>
> Date: Wed, 23 Feb 2022 12:14:52 +0800
> 
> |            |   old |   new |
> |------------+-------+-------|
> | s63        | 1.485 |  .376 |
> | s65        | 1.211 |  .990 |
> | r63        | 1.323 |  .609 |
> | r65        | 1.422 | 1.091 |
> | rand63     | 1.236 | 2.581 |
> | rand65     | 1.627 | 1.238 |
> | worst63    | 1.109 | 6.019 |
> | worst65    | 1.359 | 1.067 |
> | random100K |   160 |   101 |
> 
> 
> Observations: It all looks as expected. Its compatible with everything
> I have seen in similar comparisons you can find in the ether.
> 
> Insertion sort: great for ordered lists (factor of 2 to 4 better);
> poor for random data (factor of 2 worse); worst case is 5.4 times
> worse (theoretical it should be about 32/6 = 5.333 :) ).
> 
> Vector sort: its typically 30% faster, but does even better for longer
> lists.
> 
> Is the insertion sort for small lists worth it compared to the vector
> sort? For partially ordered lists its between 2 and 4 times faster than
> the vector sort. For random data its a factor of 2 slower. The worst
> case is a factor of 6. I think its worth it (my prejudice is the data is
> more likely to be partially ordered than not.)  Also the advantage of
> the insertion sort shown here is really the worst case---its more
> advantageous for even shorter lists where the overhead of converting to
> and from the list becomes more important.

The 5-fold slowdown is a pain, IMO.  Can we do better in the worst
case?

> And implementing TIMSORT will be even better---similar or better speedup
> for the best cases, and only marginal degradation of the worst.  But I
> think even this small change here is a win.

Can we see the numbers?  This sounds like a net win to me.

Thanks.