Fastest sort of fixed length 6 int array
stackoverflow.com
stackoverflow.com
$ gcc -O3 sortnet -o sortnet && ./sortnet
sort6_sorting_network_v4: time = 988 cycles
sort6_sorting_network_per: time = 390 cycles
His benchmarking harness also leaves a lot to be desired. But that's another issue. He also says that this is eventually intended for use on a GPU, but he's ranking the implementations by performance on a deeply pipelined out-of-order CPU. Modern GPU cores have some minimal scoreboarding but none of them do the full dance of register renaming and decoupled execution units.
I'd never never heard of sorting networks or oblivious sorting before, and it's good to see some answers other than "Quicksort!"
I _have_ read about quicksort. Some of these other methods, not so much.
That for me makes this a useful and interesting story.
(Worst-case in the input, averaged over your random bits.)
http://www.cs.duke.edu/~reif/courses/alglectures/skiena.lect...
I don't know that I've actually experienced a worst-case quicksort situation but I do know of a particular job using quicksort that ran far, far too long - indeed it never completed the quicksort step, because...
After 6 hours of sorting (all previous runs had completed the sort step in 40 minutes or less) we finally killed it, changed the sort implementation, fired it up again and never had the same problem again. It was an enterprise time-critical job running on a mainframe that simply had to complete within 24 hours of start.
Then a sufficiently smart compiler can decide to assign, say, %eax to x and %ebx to y, and then just rename its notion of registers, and after the swap just begin using %ebx for x and %eax for y. A swap with no copies at all!
(It won't do this in every case, and it depends on context, but such an optimization is possible... but not with xor swaps.)
And where conditionals are costly, you can use tricks like:
float temp = min(x, y);
x = max(x, y);
y = temp;