On Mon, Oct 15, 2012 at 1:04 PM, Era Scarecrow <rtcv...@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.
