Sunday, September 13, 2015

12 depth sorting network that might extend to any power of 2

This wikipedia article gives a pretty good introduction to the topic:

The above is a very symmetrical pattern that I've proven by exhaustion with the computer can sort every binary sequence of 1's and 0's (65536 of them in all) which by the 0 and 1 principle means it can sort every list of 16 orderable items.

The pattern above can be broken down into 3 regimes... First is a log(n) size step that looks like a binary tournament in reverse order, and the second is one also of size log(n) that looks like a binary tournament where the lowest seeds are matched with the highest seeds, Then finally there is a bubble sort like regime. So the runtime is 2*log(n) +4 or possible 3*log(n) if the 4 has to be enlarged for larger n... And the best known currently is odd-even merge sort which is log(n)^2... For 16 items this works out to approximately the same but hopefully for larger n the improvement will hold... And a better number of comparators at roughly n*(2*log(n)+4) vs. n*(log(n))^2.

No comments:

Post a Comment