There is :) For example if you look at the second column of the table at http://users.telenet.be/bertdobbelaere/SorterHunter/sorting_networks.html you can see that at some point the smallest network is deeper and the shallowest is larger, so you get multiple size/depth combinations that make up the Pareto front of optimal networks. For 10 and 12 channels we know via https://arxiv.org/abs/1806.00305 that the shallowest network cannot be made as small as the smallest network overall.
I personally haven’t looked at optimizing for depth or combinations of size and depth so far, so I don’t know any further details about that.
Wow, this is cool stuff. I’m entirely unfamiliar with the subject but already see some connections to what I already know.
Completely off-topic, I really enjoy looking at sorting diagrams, how are these drawn? I have the urge to make a screensaver that generates and displays random sorting diagrams using round brackets.
I’m using TikZ which is a (La)TeX package for drawing figures. I haven’t completely automated this though, i.e. I have TikZ macros for the individual elements, but place them individually and manually. For something automated like what you have in mind I’d probably generate SVGs directly or look into something like d3.
Thank you for writing this up so clearly! I look forward to reading the later parts :)
If you do turn them into circuits, is there a trade off between depth and the total number of comparators spent?
There is :) For example if you look at the second column of the table at http://users.telenet.be/bertdobbelaere/SorterHunter/sorting_networks.html you can see that at some point the smallest network is deeper and the shallowest is larger, so you get multiple size/depth combinations that make up the Pareto front of optimal networks. For 10 and 12 channels we know via https://arxiv.org/abs/1806.00305 that the shallowest network cannot be made as small as the smallest network overall.
I personally haven’t looked at optimizing for depth or combinations of size and depth so far, so I don’t know any further details about that.
Thanks!
This is super interesting and I’m looking forward to your follow up posts. ❤️
This is exceptional.
Wow, this is cool stuff. I’m entirely unfamiliar with the subject but already see some connections to what I already know.
Completely off-topic, I really enjoy looking at sorting diagrams, how are these drawn? I have the urge to make a screensaver that generates and displays random sorting diagrams using round brackets.
I’m using TikZ which is a (La)TeX package for drawing figures. I haven’t completely automated this though, i.e. I have TikZ macros for the individual elements, but place them individually and manually. For something automated like what you have in mind I’d probably generate SVGs directly or look into something like d3.