My profilings:
reordering took 1003000 nsreordering took 51000 nsreordering took 59000 nsreordering took 62000 nsreordering took 74000 ns
The first "reordering" that was done was even the most trivial among all those (only 3 elements to reorder).
EDIT: It gets even better. There seems to be a second optimization phase after which the speed triples:
reordering took 1075000 ns // first runreordering took 54000 nsreordering took 64000 nsreordering took 70000 nsreordering took 92000 nsreordering took 89000 nsreordering took 90000 nsreordering took 139000 nsreordering took 109000 nsreordering took 103000 nsreordering took 93000 nsreordering took 93000 nsreordering took 1872000 ns // 2nd optimization?reordering took 26000 nsreordering took 24000 nsreordering took 24000 nsreordering took 25000 nsreordering took 28000 nsreordering took 25000 nsreordering took 23000 ns