Sorting algorithms

[Philippe Sigaud]

On Mon, Oct 15, 2012 at 5:52 PM, Andrei Alexandrescu
<SeeWebsiteForEmail at erdani.org> wrote:

> 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.

Here:

http://dpaste.dzfl.pl/42fac981

I don't know if the benchmarking code is OK. I substract a reference
because randomly shuffling an array takes some time.

Results for my computer (smaller ratio means faster network sort
compared to std.algorithm.sort)

Size 1, network: 2.10, std.algorithm.sort: 15.86, ratio network/std.algo: 0.13
Size 2, network: 2.23, std.algorithm.sort: 14.26, ratio network/std.algo: 0.16
Size 3, network: 6.22, std.algorithm.sort: 20.75, ratio network/std.algo: 0.30
Size 4, network: 8.25, std.algorithm.sort: 28.36, ratio network/std.algo: 0.29
Size 5, network: 18.54, std.algorithm.sort: 39.02, ratio network/std.algo: 0.48
Size 6, network: 20.12, std.algorithm.sort: 45.58, ratio network/std.algo: 0.44
Size 7, network: 27.49, std.algorithm.sort: 55.53, ratio network/std.algo: 0.50
Size 8, network: 33.91, std.algorithm.sort: 66.02, ratio network/std.algo: 0.51
Size 9, network: 53.98, std.algorithm.sort: 75.54, ratio network/std.algo: 0.71
Size 10, network: 46.66, std.algorithm.sort: 81.68, ratio network/std.algo: 0.57
Size 11, network: 65.06, std.algorithm.sort: 111.25, ratio
network/std.algo: 0.58
Size 12, network: 66.31, std.algorithm.sort: 109.40, ratio
network/std.algo: 0.61
Size 13, network: 74.84, std.algorithm.sort: 115.94, ratio
network/std.algo: 0.65
Size 14, network: 90.05, std.algorithm.sort: 131.84, ratio
network/std.algo: 0.68
Size 15, network: 95.23, std.algorithm.sort: 145.31, ratio
network/std.algo: 0.66
Size 16, network: 104.66, std.algorithm.sort: 162.84, ratio
network/std.algo: 0.64
Size 17, network: 125.30, std.algorithm.sort: 167.49, ratio
network/std.algo: 0.75
Size 18, network: 133.10, std.algorithm.sort: 182.20, ratio
network/std.algo: 0.73
Size 19, network: 143.92, std.algorithm.sort: 195.58, ratio
network/std.algo: 0.74
Size 20, network: 155.01, std.algorithm.sort: 211.59, ratio
network/std.algo: 0.73
Size 21, network: 171.43, std.algorithm.sort: 224.47, ratio
network/std.algo: 0.76
Size 22, network: 177.46, std.algorithm.sort: 236.92, ratio
network/std.algo: 0.75
Size 23, network: 192.22, std.algorithm.sort: 253.38, ratio
network/std.algo: 0.76
Size 24, network: 205.39, std.algorithm.sort: 270.83, ratio
network/std.algo: 0.76
Size 25, network: 213.25, std.algorithm.sort: 281.01, ratio
network/std.algo: 0.76
Size 26, network: 233.96, std.algorithm.sort: 283.57, ratio
network/std.algo: 0.83
Size 27, network: 246.73, std.algorithm.sort: 297.67, ratio
network/std.algo: 0.83
Size 28, network: 260.41, std.algorithm.sort: 313.88, ratio
network/std.algo: 0.83
Size 29, network: 280.06, std.algorithm.sort: 321.01, ratio
network/std.algo: 0.87
Size 30, network: 298.65, std.algorithm.sort: 342.55, ratio
network/std.algo: 0.87
Size 31, network: 308.09, std.algorithm.sort: 355.70, ratio
network/std.algo: 0.87
Size 32, network: 323.89, std.algorithm.sort: 380.31, ratio
network/std.algo: 0.85

On the computers I tested it (Windows, Linux, different machines), the
cutoff is at about 35-38 elements.