Monday, June 8, 2015

Symetrical sorting network

This is a sorting network of 67 comparators and 10 depth, but with the obvious symmetry it suggests that there might be designs that can be found for any power of 2... The lighter colored part is how a lot of the best designs start, the rest is what I came up with to finish it...
To make the pattern more complete but less optimal, there can be added a group of comparisons distance 5 apart between the group of 6 apart and 4 apart, so I'll conjecture that it's always possible to make a network extending the pattern above of log[2](n)+n/2 depth for N a power of 2, though I'm not sure about the total number of comparators because as you can see in the above they decreased in number down to when the comparisons were 3 apart when they suddenly went all the way across... And then again when they were 1 apart... Maybe that always happens when the comparators are n/(2^i) - 1 apart for i greater than or equal to 2? I'm not sure, a 32 item network would be really hard to test because of the size of 2^32, maybe there can be some proofs constructed to determine that... Or alternatively maybe just build one according to the plan described for 1024 items and try a great number of random arrangements of that many items and if it sorts them all there's a good probability it always works...

No comments:

Post a Comment