Fastest sort of fixed length 6 int array
stackoverflow.com
Fastest sort of fixed length 6 int array
1–10 of 18 posts
Re: Fastest sort of fixed length 6 int array
#2Wow, thanks for the link. I'd never heard of sorting networks before. The first thing I thought of was "use an XOR swap to cut memory accesses"...
Re: Fastest sort of fixed length 6 int array
#3could anyone recommend some reading on theory and implementation of sorting networks?
Re: Fastest sort of fixed length 6 int array
#4could anyone recommend some reading on theory and implementation of sorting networks?
Knuth's TAOCP covers it in vol III of recent editions. (http://www-cs-staff.stanford.edu/~uno/taocp.html)
Re: Fastest sort of fixed length 6 int array
#5Wow, thanks for the link. I'd never heard of sorting networks before. The first thing I thought of was "use an XOR swap to cut memory accesses"...
I don't think that optimization helps when you have a spare register to use as a temp value.
Re: Fastest sort of fixed length 6 int array
#6This is the sort of stuff that's great to read because you can't help but learn something.
I'd never never heard of sorting networks or oblivious sorting before, and it's good to see some answers other than "Quicksort!"
Re: Fastest sort of fixed length 6 int array
#7This is the sort of stuff that's great to read because you can't help but learn something. I'd never never heard of sorting networks or oblivious sorting before, and it's good to see some answers other than "Quicksort!"
Surely by now you have read that quicksort's worst-case behavior is O(n2)?
Re: Fastest sort of fixed length 6 int array
#8This is the sort of stuff that's great to read because you can't help but learn something. I'd never never heard of sorting networks or oblivious sorting before, and it's good to see some answers other than "Quicksort!"
Surely by now you have read that quicksort's worst-case behavior is O(n 2)?
But thats sort of the point.
I _have_ read about quicksort. Some of these other methods, not so much.
That for me makes this a useful and interesting story.
Re: Fastest sort of fixed length 6 int array
#9To be a little more speculative . . . if it is on GPU, is there some way of using rendering operations? The 'hidden-surface problem' in graphics has been described as basically a sorting problem: so represent each number as a triangle Z . . . well, maybe it would not be very fast, but you could do a few million at once!
Re: Fastest sort of fixed length 6 int array
#10Wow, thanks for the link. I'd never heard of sorting networks before. The first thing I thought of was "use an XOR swap to cut memory accesses"...
If you do the naive implementation:
int temp = x;
x = y;
y = temp;
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.)