Sorting Networks On Restricted Topologies

Indranil Banerjee, Dana Richards, Igor Shinkar

The sorting number of a graph with $n$ vertices is the minimum depth of a sorting network with $n$ inputs and outputs that uses only the edges of the graph to perform comparisons.…