Sorting with networks of data structures
We consider the problem of sorting a permutation using a network of data structures as introduced by Knuth and Tarjan. In general the model as considered previously was restricted to networks that are directed acyclic graphs (DAGs) of stacks and/or queues. In this paper we study the question of which are the smallest general graphs that can sort an arbitrary permutation and what is their efficiency. We show that certain two-node graphs can sort in time ?(n2) ? ( n 2 ) and no simpler graph can sort all permutations. We then show that certain three-node graphs sort in time ?(n3/2) ? ( n 3 / 2 ) , and that there exist graphs of k k nodes which can sort in time ?(nlogkn) ? ( n log k n ) , which is optimal.
data structures sorting networks