Sorting algorithms

[Andrei Alexandrescu]

On 10/15/12 8:11 AM, Philippe Sigaud wrote:
> On Mon, Oct 15, 2012 at 1:04 PM, Era Scarecrow<rtcvb32 at yahoo.com>  wrote:
>> On Monday, 15 October 2012 at 09:18:12 UTC, Era Scarecrow wrote:
>>>
>>> So an example area to be sorted with 16 elements would take on average
>>> about 100 compares while theoretically you can do it in half that number.
>>
>>
>>   Correction. 16 numbers would be solved in about 49 compares while an
>> optimal sorting takes about 45. And for 21 numbers about 74 compares while
>> optimally about 63.
>>
>>   These numbers don't seem that large, but at the same time they do.
>
> Somewhat related: I once played with sorting networks and how to
> generate them at compile time in D. It's in template tutorial on
> Github. Here are some results:
>
> https://github.com/PhilippeSigaud/D-templates-tutorial/blob/master/templates_around.tex#L560
>
> Discarding LaTeX markup:
>
>
> n    Sorting    Standard    ratio
>       network    sort
> 5    324        532         1.642
> 10   555        1096        1.975
> 15   803        1679        2.091
> 20   1154       2314        2.005
> 25   1538       3244        2.109
> 30   2173       3508        1.614
> 35   4075       4120        1.011
> 40   5918       5269        0.890
> 45   7479       5959        0.797
> 50   9179       6435        0.701
>
> Were n is the (predetermined) number of elements in an array and a
> ratio of 2.0 means sorting networks are twice faster than
> std.algo.sort in this particular case.

I wanted to investigate small sorts using sorting networks for ages, but 
never got around to it. That's important for quicksort because it 
produces many small arrays that need sorting.

Could you also test for very small sizes (2 to 4) and essentially test 
for 1-increment speed up to, say, 30 elements? I assume that's where the 
major wins come. I think we could use CT-generated sorting networks for 
arrays below a specific size. The converse risk is growth of generated code.


Andrei